問題
http://community.topcoder.com/stat?c=problem_statement&pm=11154&rd=14435
スライムの島が複数あり、各島ごとに何匹スライムがいるかわかっている。
各島を１つに統合したい。
２つの島を統合するとき、もう一つの島にいるスライムの数以上であれば
その島の名前をつけることができる。
このとき、最大で何通りの島の数が存在しうるか求める。
解き方
配列をソートし、初期値をその名前を残したい島のスライムの数とする。
小さい方から統合していき、すべての島を統合できればその名前は残り、
そうでなければその名前は残らなくなる。
コード
class SlimeXSlimesCity {
public: int merge(vector<int> population) {
int n=population.size();
int ret=0;
sort(all(population));
FORE(i,0,n){
long long sum=population[i];
int at=0;
while(at<n){
if(at==i){
at++;
}
else if(sum>=population[at]){
sum+=population[at];
at++;
}
else break;
}
if(at>=n)ret++;
}
return ret;
}
};
public: int merge(vector<int> population) {
int n=population.size();
int ret=0;
sort(all(population));
FORE(i,0,n){
long long sum=population[i];
int at=0;
while(at<n){
if(at==i){
at++;
}
else if(sum>=population[at]){
sum+=population[at];
at++;
}
else break;
}
if(at>=n)ret++;
}
return ret;
}
};
Share this
Related Posts
SRM 592 DIV1 Easy - LittleElephantAndBalls
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12758&rd=15704
解き方
問題文を、最終的にボールを置いた位置の状態に- SRM 539 DIV1 Easy - Over9000Rocks
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11855&rd=14731
解き方
９０００以上となる数をすべて保存しては間に合
- SRM 587 DIV1 Easy - JumpFurther
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12300&rd=15699
解き方
最初はすべてのターンでジャンプし、そのときb
- SRM 516 DIV1 Easy - NetworkXOneTimePad
問題
http://community.topcoder.com/stat?c=problem_statement&pm=10846&rd=14541
解き方
すべての暗号前の文字と暗号後の文字の組み合わ