SRM 582 DIV1 Easy - SpaceWarDiv1

SRM 582 DIV1 Easy - SpaceWarDiv1

16:15

問題


http://community.topcoder.com/stat?c=problem_statement&pm=12604&rd=15502

魔法少女が敵を倒す。
それぞれの敵には強さとその強さの個体数、それぞれの魔法少女は強さを持つ。
魔法少女は自分よりも強さが敵を倒すことができる。
その際、その魔法少女の疲れの値が１増える。

このとき、魔法少女が敵を全て倒したときの疲れの最小値を求める。
全て倒せないときはー１を返す。

解き方


疲れの値を２分探索させて、最小の疲れの値を求める。

敵の数が最大１０＾１４のため、
その疲れの値が有効かどうかの関数の実装に注意。

降順のソートには「sort(rbegin(),rend()) 」が利用可能。
long longの値を扱うには数字の後に「1234567890LL」とLLをつける。

コード


class SpaceWarDiv1 {

public:
bool ispossible(long long maxbattle,vector<int> &girls,vector<pair<int,long long> > &enemies){
long long girlnum=maxbattle,enemynum=enemies[0].second;
int gi=0,ei=0;

while(gi<girls.size() && ei<enemies.size()){
if(girlnum==0){
gi++;
girlnum=maxbattle;
}
if(enemynum==0){
if(ei==enemies.size()-1)return true;
ei++;
enemynum=enemies[ei].second;
}
if(girls[gi]<enemies[ei].first){
gi++;
continue;
}
long long battle=min(girlnum,enemynum);
girlnum-=battle;
enemynum-=battle;
}

return false;
}

long long minimalFatigue(vector<int> girls, vector<int> enemyStrength, vector<long long> enemyCount) {
vector<pair<int,long long> > enemies;
long long h=1e+18,l=0;

enemies.clear();
FORE(i,0,enemyStrength.size())enemies.push_back(make_pair(enemyStrength[i],enemyCount[i]));
sort(girls.rbegin(),girls.rend());
sort(enemies.rbegin(),enemies.rend());

if(girls[0]<enemies[0].first)return -1;

while(h-l>0){
long long m=(h+l)/2;
if(ispossible(m,girls,enemies))h=m;
else l=m+1;
}

return h;
}

};

Share this

Google Facebook Twitter More

Related Posts

Next
« Prev Post
Previous
Next Post »