SRM506 Div2 Medium (500) SlimeXSlimesCity

案外簡単だった.
入力がソートされているとすごく簡単に理解できる.
最大値から順番にマージしていくと,最大値のインデックスが最後まで残る.
もし,最大値未満の値の総和が最大値以上だった場合,最大値を最後に選べば,最大値以外のインデックスが最後まで残る.
もし,上記の条件に当てはまった場合0〜n-2までの部分問題を解けばいいので再帰的に計算できる.

# 最初sumの計算にlongを使ってたが桁あふれした
# longが4バイトだって初めて知ったよorz

class SlimeXSlimesCity {
public:
  int merge(vector <int> population) {
    int res = 0;
    int n = population.size();
    int i,j;
    sort(population.begin(), population.end());
    // for(i = 0; i < n; i++) cout << population[i] << ",";
    // cout << endl;
	for(i = n-1; i >= 0 ;i--){
      res++;
      long long sum = 0;
      for(j = 0; j < i; j++){
        sum += population[j];
      }
      if (sum >= population[i]) continue;
      break;
    }
    cout << i << endl;
    return res;
  }
};