Codeforces ECR #165 : D. Shop Game

Eまでは順調だったね。
https://codeforces.com/contest/1969/problem/D

問題

N個のアイテムがある。
各アイテムiに対し、パラメータA[i],B[i]がある。

先手はN個中いくつか選びコストA[i]で購入する。
後手はそのうちK個を選んでただで受け取り、残りをコストB[i]で買い取る。

先手の最大利益、すなわち後手が買い取ったアイテムのコストの総和から、先手が買ったアイテムのコストの総和の差の最大値を求めよ。

解法

アイテムをB[i]の大きい順に並べる。
後手は当然ただで受け取るものはB[i]の大きなK個を選ぶ。

そこで、先頭j個のうちK個まで後手がただで受け取ると仮定すると、残り(N-j)個は後手に買わせることができる。
先手は、先頭j個のうちA[i]の小さいK個を選び、残り(N-j)個は損しない範囲で全部買うと考えてよい。
これをjを走査しながらそれぞれ計算していこう。

int T,N,K;
int A[202020],B[202020];
pair<int,int> C[202020];
ll S[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		FOR(i,N) cin>>A[i];
		FOR(i,N) cin>>B[i];
		FOR(i,N) C[i]={B[i],A[i]};
		sort(C,C+N);
		
		FOR(i,N) {
			S[i+1]=S[i]+max(0,C[i].first-C[i].second);
		}
		ll ret=0;
		ll suma=0;
		multiset<int> As;
		if(K==0) ret=S[N];
		for(i=N-1;i>=0;i--) {
			suma+=C[i].second;
			As.insert(C[i].second);
			if(As.size()>K) {
				suma-=*As.rbegin();
				As.erase(As.find(*As.rbegin()));
			}
			if(As.size()==K) {
				ret=max(ret,S[i]-suma);
			}
		}
		cout<<ret<<endl;
		
	}
}

まとめ

K個だけ好きにタダでもらえるとか、そんな売り買いの仕方ありか？とは思う。