SRM 506 DIV1 Easy - SlimeXSlimesCity

問題


http://community.topcoder.com/stat?c=problem_statement&pm=11154&rd=14435

スライムの島が複数あり、各島ごとに何匹スライムがいるかわかっている。
各島を1つに統合したい。
2つの島を統合するとき、もう一つの島にいるスライムの数以上であれば
その島の名前をつけることができる。

このとき、最大で何通りの島の数が存在しうるか求める。

解き方


配列をソートし、初期値をその名前を残したい島のスライムの数とする。
小さい方から統合していき、すべての島を統合できればその名前は残り、
そうでなければその名前は残らなくなる。

コード


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;
}

};

Share this

Related Posts

Previous
Next Post »