Codeforces #854 : F. Halve or Subtract

コードは短いんだけどね。
https://codeforces.com/contest/1799/problem/F

問題

整数列Aと、整数値B,K1,K2が与えられる。

整数列の要素を指定し、以下の処理を行うことを考える。

• type1: A[i]をceil(A[i]/2)で置き換える
• type2: A[i]をmax(A[i]-B,0)で置き換える。

各要素に対し、type1,2の処理はそれぞれ1回までしか行えない。
また、前者はK1回、後者はK2回までしか行えないとする。

最終的にAの総和を最小化したとき、その値を求めよ。

解法

type1,2両方行う要素数kを総当たりしよう。
当然Aのうち大きい順にk個選ぶ。
あとは、残された要素のうちtype1とtype2の効果の差をソートし、type2の方が効果が得られる要素(K2-k)個を優先的に選んでいこう。

int T,N,B,K1,K2,A[5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>B>>K1>>K2;
		ll S=0;
		FOR(i,N) {
			cin>>A[i];
			S+=A[i];
		}
		sort(A,A+N);
		reverse(A,A+N);
		ll ma=0;
		for(i=0;i<=min(K1,K2);i++) {
			ll sum=0;
			FOR(j,i) sum+=min(A[j],A[j]/2+B);
			int L1=K1-i;
			int L2=K2-i;
			if(L1+L2+i>N) continue;
			vector<pair<int,int>> V;
			for(j=i;j<N;j++) {
				if(j<i+L1+L2) V.push_back({A[j]/2-min(A[j],B),-A[j]});
			}
			sort(ALL(V));
			FOR(j,L2) sum+=min(-V[j].second,B);
			FOR(j,L1) sum+=(-V[L2+j].second)/2;
			ma=max(ma,sum);
		}
		cout<<S-ma<<endl;
		
		
	}
}

まとめ

落ち着いて考えるとそこまで難しくないんだけどね。