SRM 582 Div1 Easy SpaceWarDiv1
問題
魔法少女たちがおり、彼女らの力がvector int で与えられる。敵が複数おり、強さenemyStrength[i]の敵がenemyCount[i]匹いる。魔法少女達は自分と同じか自分より弱い敵を倒すことができ、一体倒すにつき疲労度が+1される。敵をすべて倒した時にもっとも疲労度の高い魔女の疲労度をFとする。Fを最小化せよ。
やりかた
二分探索でいける。Fを固定した時に、そのFの疲労度のうちで敵を倒せるかどうか判定して、倒せるようならもうすこしFを小さくしてみて、倒しきれないようならFをもう少し大きくしてみる。これをくりかえす。判定の仕方としては少女[i]が倒せる敵の数をFを上限にして倒す。これをすべての少女について行なってみて、その時のFで敵を残らず倒せるかどうか調べればいい。
class SpaceWarDiv1 { public: long long minimalFatigue(vector <int> magicalGirlStrength, vector <int> enemyStrength, vector<long long> enemyCount) { int N = magicalGirlStrength.size(); int M = enemyStrength.size(); vector<pair<ll, ll> > sc; for(int i = 0; i < M; i++) sc.push_back(make_pair(enemyStrength[i], enemyCount[i])); sort(ALL(magicalGirlStrength)); sort(ALL(sc)); ll lb = 1, ub = (ll)1e18; while(ub != lb){ ll mid = (lb + ub) / 2; vector<ll> rem; for(int i = 0; i < M; i++) rem.push_back(sc[i].second); for(int i = 0; i < N; i++){ ll tmp = mid; for(int j = 0; j < M; j++){ if(sc[j].first <= magicalGirlStrength[i]){ ll kill = min(tmp, rem[j]); rem[j] -= kill; tmp -= kill; } } } if(count(ALL(rem), 0) == M) ub = mid; else lb = mid + 1; } return lb == (ll)1e18 ? -1 : lb; } };
出場できなかったので練習。
最初、
ll kill = min(tmp, rem[j]); rem[j] -= kill; tmp -= kill;
を
rem[j] -= min(tmp, rem[j]); tmp -= min(tmp, rem[j]);
として、一時退避をおこなっていなかったため、どうしても答えが合わなかった。
Get up! 明日のSUPER ST@R!