SRM 582 DIV1 Easy - SpaceWarDiv1 (復習×○)
問題
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;
}
};
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;
}
};
