Fの方が考えずにできたかも。
https://atcoder.jp/contests/abc160/tasks/abc160_e
問題
赤いリンゴA個、緑のリンゴB個、無色のリンゴC個がある。
それぞれのおいしさが与えられる。
無色のリンゴを赤か緑任意に塗ったのち、赤いリンゴをX個、緑のリンゴをY個選んだとき、おいしさの最大値を求めよ。
解法
リンゴのおいしさの小さい順に見て、「これを選ばないと必要な個数選べない」となったらそのリンゴを選ぼう。
A,B,Cは未処理のリンゴ数、X,Yは残りから選ばないといけないリンゴ数とする。
- 今見ているリンゴが赤いとき、以下の条件で選ぶ。
- これを選ばないと赤が足りなくなる(A+C==X)とき
- これを選ばないと総数が足りなくなる(A+B+C==X+Y)とき
- これを選ばないと緑が足りなくなるときで赤も余裕がないとき(A==XかつB+C==Y)とき
- 緑の場合は、上記条件を赤と緑入れ替える。
- 今見ているリンゴが無色の時、
- これを選ばないと赤・緑・総数が足りなくなる時、余裕が比較的ある方に塗ったうえで選択する。
int X,Y,A,B,C; vector<pair<int,int>> E; void solve() { int i,j,k,l,r,x,y; string s; cin>>X>>Y>>A>>B>>C; FOR(i,A) cin>>x, E.push_back({x,0}); FOR(i,B) cin>>x, E.push_back({x,1}); FOR(i,C) cin>>x, E.push_back({x,2}); sort(ALL(E)); ll ret=0; FORR(e,E) { x=e.second; y=e.first; if(x==0) { if(A+C==X || (B+C==Y&&A==X) || A+B+C==X+Y) { X--; ret+=y; } A--; } else if(x==1) { if((A+C==X&&B==Y) || B+C==Y || A+B+C==X+Y) { Y--; ret+=y; } B--; } else { if(A+C==X || B+C==Y || A+B+C==X+Y) { if(A<X) { X--; } else if(Y) { Y--; } ret+=y; } C--; } } cout<<ret<<endl; }
まとめ
最初大きい順にやってしまい混乱した。