SRM582 Div1 Easy(250) SpaceWarDiv1
SpaceWarDiv1
疲労度で二分探索。最大の疲労度が与えられたとき、魔法少女が敵を倒せるかどうかは、弱い魔法少女をなるべく弱い敵に貪欲に割り当てて行けば分かる。
#include <vector> #include <algorithm> #include <utility> using namespace std; bool check( vector<int> girl, vector<int> enemy, vector<long long> count, long long f ) { for ( int i=0; i<(int)girl.size(); i++ ) { long long t = f; for ( int j=0; j<(int)enemy.size(); j++ ) if ( girl[i]>=enemy[j] ) { long long n = min(t,count[j]); t -= n; count[j] -= n; } } for ( int i=0; i<(int)enemy.size(); i++ ) if ( count[i]>0 ) return false; return true; } class SpaceWarDiv1{public: long long minimalFatigue( vector <int> magicalGirlStrength, vector <int> enemyStrength, vector<long long> enemyCount ) { sort( magicalGirlStrength.begin(), magicalGirlStrength.end() ); vector<pair<int,long long> > T; for ( int i=0; i<(int)enemyStrength.size(); i++ ) T.push_back(make_pair(enemyStrength[i],enemyCount[i])); sort(T.begin(),T.end()); for ( int i=0; i<(int)enemyStrength.size(); i++ ) enemyStrength[i] = T[i].first, enemyCount[i] = T[i].second; if ( !check(magicalGirlStrength,enemyStrength,enemyCount,1LL<<62) ) return -1; long long ans = (1LL<<62)-1; for ( long long b=1LL<<61; b>0; b>>=1 ) if ( check(magicalGirlStrength,enemyStrength,enemyCount,ans-b) ) ans -= b; return ans<(1LL<<62)-1 ? ans : -1; }};