SRM582 Div1 Easy "SpaceWarDiv1"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12604
訳
魔法少女はマジカルパワーを生まれ持った女の子である。地球を守るため、彼女たちは今日も戦う。宇宙からの敵は今まさに地球を侵略しようとしており、魔法少女たちはそれに立ち向かっている。
あなたは魔法少女のステータスであるint magicalGirlStrengthが与えられる。magicalGirlStrength[i]はi番目の少女の強さを表す。あなたは敵のステータスをであるint enemyStrengthとint[] enemyCountが与えられる。enemyStrenth[i]の強さを持った敵が、enemyCount[i]だけ出現している事を表す。
各魔法少女は常に1対1で敵と戦っている。魔法少女は敵の強さ以上の強さを持っている場合、その敵に打ち勝つ事が出来る。
戦いが始まるとき、彼女らの疲労度は0である。彼女らは敵を倒すたびに、疲労度が1増加してしまう。
魔法少女たちの目標は全ての敵を倒す事である。それは、各敵は誰か1人の魔法少女によって打ち負かされなければならない。さらに、魔法少女たちは、戦いが終わった後の、最大の疲労度を最小化したい。
全ての敵を倒す事が出来なければ-1を返せ。そうでなければ、最小化した最大の疲労度を返せ。
制約
1 <= 魔法少女の数 <= 50
1 <= 魔法少女の強さ <= 10000
1 <= 敵の強さの種類 <= 50
1 <= 敵の強さ <= 10000
1 <= 敵の各強さのその出現数 <= 10^14
考えた事
敵の数がくっそ多いから、この疲労度でいけるかな~つって2分探索していく。
ソースコード
class SpaceWarDiv1 { public: long long minimalFatigue(vector <int> mgs, vector <int> es, vector<long long> ec){ // 強さを降順にソート int N = mgs.size(); sort( mgs.begin(), mgs.end(), greater<int>() ); int M = es.size(); for( int i = 0; i < M; i++ ){ for( int j = 0; j < M - 1; j++ ){ if( es[j] < es[j+1] ){ swap( es[j], es[j+1] ); swap( ec[j], ec[j+1] ); } } } // めっさ強い敵がいたら地球滅亡 if( mgs[0] < es[0] ) return -1LL; // 敵の数の総和をだしておく for( int i = 1; i < M; i++ ){ ec[i] += ec[i-1]; } // 2分探索 long long h = ec[M-1]; long long l = 1; while( l <= h ){ long long m = (h + l) / 2; // 疲労度mで殲滅できないかな~ bool ok = false; long long cnt = 0; for( int i = 0; i < N; i++ ){ // 敵の強さを出す int eid = 0; while( ec[eid] <= cnt ){ eid++; } // 敵が魔法少女より強い if( mgs[i] < es[eid] ) break; // 敵をmだけ討伐 cnt += m; // 敵を全て倒した if( ec[M-1] <= cnt ){ ok = true; break; } } if( ok ){ h = m - 1; }else{ l = m + 1; } } return l; } };