これはFよりだいぶ楽だった。
https://atcoder.jp/contests/abc289/tasks/abc289_g
問題
N人の客がおり、i番の客の購買意欲はB[i]である。
店にはM種の商品がある。各商品について、以下の問いに答えよ。
商品価値Cが与えられる。
この商品の価格をPとしたとき、客はB[i]+C≧Pなら、金額Pを出して買ってくれる。
Pを適切に設定したとき、売り上げの最大値を求めよ。
解法
客を昇順にソートしておく。
もしP=B[i]+Cにしたとき、買ってくれる人は(N-1-i)人なので、売り上げは(B[i]+C)*(N-1-i)となる。
これはCに対する一次関数の最大化問題になるので、ConvexHullTrickで解ける。
int N,M; ll B[202020],C[202020]; template<typename V> struct ConvexHull { deque<pair<V,V>> Q; V calc(pair<V,V> p, V x) { return p.first*x+p.second; } int dodo(pair<V,V> A,pair<V,V> B, pair<V,V> C) { return ((__int128)(B.second-C.second)*(B.first-A.first)<=(__int128)(A.second-B.second)*(C.first-B.first)); } void add(V a, V b) { // add ax+b if(Q.size() && Q.back().first==a) { //aが同じ場合 //if(b>=Q.back().second) return; //minの場合 if(b<=Q.back().second) return; //maxの場合 Q.pop_back(); } Q.push_back({a,b}); int v; while((v=Q.size())>=3 && dodo(Q[v-3],Q[v-2],Q[v-1])) Q[v-2]=Q[v-1], Q.pop_back(); } void add(vector<pair<V,V>> v) { sort(v.begin(),v.end()); for(auto r=v.begin();r!=v.end();r++) add(r->first,r->second); } V query(V x) { int L=-1,R=Q.size()-1; while(R-L>1) { int M=(L+R)/2; (0^((calc(Q[M],x)<=calc(Q[M+1],x)))?L:R)=M; } return calc(Q[R],x); } }; ConvexHull<ll> ch; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,N) cin>>B[i]; sort(B,B+N); for(i=N-1;i>=0;i--) { ch.add(N-i,1LL*B[i]*(N-i)); } FOR(i,M) { cin>>x; cout<<ch.query(x)<<" "; } cout<<endl; }
まとめ
こっちは簡単。