問題
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 379 DIV1 Easy - SellingProducts
問題
http://community.topcoder.com/stat?c=problem_statement&pm=8440&rd=10800
解き方
一見すべての価格について調べる必要があり、10- SRM 448 DIV1 Easy - TheBlackJackDivOne
問題
http://community.topcoder.com/stat?c=problem_statement&pm=10615&rd=13902
解き方
探索箇所が少ないので全探索可能。
各カードに
- SRM 504 DIV1 Easy - MathContest
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11233&rd=14433
解き方
キューが連続的になっているということに気をつ
- SRM 391 DIV1 Easy - IsomorphicWords
問題
http://community.topcoder.com/stat?c=problem_statement&pm=8175&rd=11125
解き方
全ての文字について、可能な限り昇順になるように