Good Bye 2015 E. New Year and Three Musketeers
解法
greedy に解くことが出来ます。
まず, a+b+c < x となる criminal さんがいたら勝てないので -1 を返すことになります。
それでなかったら, とりあえず a <= b <= c となるようにソートします。
multiset に 各 criminal さんの戦闘力を詰め込みます。
a+b+c 以外で勝てない criminal さんは a+b+c で応戦するしかないので, それで応戦しましょう。応戦したら, set からその人を取り除きます。
次に, b+c か a+b+c でしか勝てない criminal さんがいることがあります。ここで a+b+c を無駄に使うのは意味がない(だったら b+c で応戦して a が倒せるやつを探したほうが良い)ので b+c でこいつには応戦します。この時, a で応戦できる criminal さんがいたら a で倒します(set から b+c 以下の criminal 及び a 以下でなるべく戦闘力の大きい criminal を 取り除く)
次に大きいのは, a+c です。これも同様に greedy 出来て, set から a+c 以下の criminal さんを取り除きましょう。同時に b で処理できるなるべく戦闘力の高い criminal も取り除いておきます。
ここからが問題です。a+b と c の大小関係はよくわからないので, a+b 以下の criminal をいじってる間に c を頑張らせる, という戦略は必ずしも正しくありません。
しかし, わかることとして, 残りの時間は「a, b, c がそれぞれバラバラに criminal を倒す時間」と「a+b, c に分かれて criminal を倒させる時間」しか残ってないことがわかります。そこで, 「a, b, c がそれぞれバラバラに criminal を倒す時間」を何回使うかで場合分けして, その場合に「a+b, c に分かれて criminal を倒させる時間」が最小で何回になるかを数えたいと思います。
a+b, c に分かれる時, criminal を倒すのにかかる最小時間を求めることを考えます。
a+b で処理できる criminal の数を x, c で処理できる criminal の数を y とします。面倒なので, x >= y と仮定します。x <= y の場合もほとんど同じです。
x-y >= y であるとします。この時は, a+b しか処理できない x-y 人をやっつけている間に, c が処理すべき分は全部倒しきれるので, かかる時間は x-y です。
そうでない場合は, a+b しか処理できない criminal を倒した後も, まだ 2*y-x 人だけ criminal は残っています。残った criminal は a+b でも c でも処理できるので, (2*y-x+1)/2 時間で残りも処理できます。よって, かかる時間は x-y+(2*x-y+1)/2 です。
int m[3], ans = 0; // least 以上だったら破壊する // その際 extra 未満の数があったらそいつも破壊 void calc(int least, int extra, multiset<int>& S) { while (!S.empty()) { auto it = S.end(); --it; if (*it < least) break; ans++; S.erase(it); it = S.lower_bound(extra); if (it != S.begin()) it--; if (*it < extra) S.erase(it); } } int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; for (int i = 0; i < 3; i++) cin >> m[i]; sort(m, m+3); multiset<int> criminal; for (int i = 0; i < n; i++) { int x; cin >> x; criminal.insert(x-1); } { auto it = criminal.end(); it--; if (*it >= m[0]+m[1]+m[2]) { cout << -1 << endl; return 0; } } calc(m[1]+m[2], -1, criminal); calc(m[0]+m[2], m[0], criminal); calc(max(m[2], m[0]+m[1]), m[1], criminal); int x = 0, y = 0; for (int el : criminal) { if (el < m[0]+m[1]) x++; if (el < m[2]) y++; } int best = 1e9; for (int i = 0; i <= n; i++) { { int z = max(x, y); int w = min(x, y); if (z-w >= w) best = min(best, i+z-w); else best = min(best, i+(z-w)+(2*w-z+1)/2); } for (int j = 0; j < 3; j++) { if (criminal.empty()) break; auto it = criminal.lower_bound(m[j]); if (it != criminal.begin()) it--; if (*it < m[j]) { if (*it < m[0]+m[1]) x--; if (*it < m[2]) y--; criminal.erase(it); } } } cout << ans+best << endl; return 0; }