SRM506 Div1Easy SlimeXSlimesCity

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

B - Colorful Creatures

ソートして人口の小さい順に並べても一般性は失われない。合併のルールから、自分より人口の少ない街は無条件に取り込めるので全て取り込むことにする。これで増えた人口でも、一つ右の街が取り込めないならば、その街が生き残ることはない。最終目標は全ての街を合併することなので、右端から判定を見ていき断層ができるまでの数が答え。下はサンプル5の解釈。

#include <bits/stdc++.h>
using namespace std;

class SlimeXSlimesCity {
public:
   int merge( vector <int> population ) {
       int n=population.size();
       sort(population.begin(),population.end());
       population.push_back(0);

       bool b[n];
       long long sum=0;
       for(int i=0;i<n;i++){
           sum+=population[i];
           if(sum>=population[i+1]) b[i]=1;
           else b[i]=0;
       }
       int ans=0;
       for(int i=n-1;i>=0;i--){
           if(b[i]) ans++;
           else break;
       }
       return ans;
   }
};