問題
個の街がありそれぞれには人口が定められている。
- 2つの街を選んで人口の小さい方を大きい方へ統合する
操作を街が1つになるまで繰り返したとき、最終的に残り得る街の数を求めよ。
解法
人口が大きい順にソートして、人口が自分以下の街の人口の和が次に大きい人口を超えているかどうかを見えていけば良い。超えられなかったときそこまでで打ち切り。
反省
AtCoder Grand Contest 011 B - Colorful Creaturesと全く同じなので悩む余地がなかった。その時より簡単な方針で書けたので経験が活きている。
コード
#include"bits/stdc++.h" using namespace std; using ll = int64_t; class SlimeXSlimesCity { public: int merge(vector <int> population) { sort(population.begin(), population.end(), greater<int>()); ll sum = accumulate(population.begin(), population.end(), (ll)0); int ans = 1; sum -= population[0]; for (int i = 1; i < population.size(); i++) { if (sum < population[i - 1]) { break; } ans++; sum -= population[i]; } return ans; } };