SRM 506 div2 mid SlimeXSlimesCity

program topcoder

問題

http://www.topcoder.com/stat?c=problem_statement&pm=11154&rd=14435 (要ログイン)

  • 初期状態の都市のサイズが population[i] (i = 0, .., N-1) で与えられる。
  • 任意の順番で、都市を2つづつ選び、それらを併合して1つの都市にする。最終的に1つだけが残るまで続ける。
    • 新しい都市の名前は、常に大きい方の都市の名前とする
    • 併合される都市のサイズが同じ時は、どちらの名前を残してもよい。
  • 最後に残る都市の名前としてあり得るのは何種類？

方針

都市 i に対して、最小の都市を順番に併合していく。この時、全ての都市を併合する前に都市 i が最小となってしまったら、どうやっても都市 i が残ることは出来ない。

回答

#include <list>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iterator>


using namespace std;
typedef unsigned long long ull;

class SlimeXSlimesCity{
public:
  int merge(vector <int> population){
    sort(population.begin(), population.end());
    const size_t n = population.size();
    vector<ull> v(n);
    copy(population.begin(), population.end(), v.begin());
    int ret = 0;
    for(size_t i = 0; i < n; ++i){
      if(check(v, i)){
	ret++;
      }
    }
    return ret;
  }

  bool check(vector<ull> l, size_t pos){
    size_t i;
    for(i=0; i < pos; ++i){
      l[pos] += l[i];
    } // i = pos
    while(i < l.size() - 1){
      if(l[i + 1] <= l[i]){
	l[i + 1] += l[i];
	i++;
      }
      else{
	break;
      }
    }
    return i == (l.size() - 1);
  }



};