AGC011_B Colorful Creatures

• 方針
  昇順にソートして、それぞれの累積和を計算しておく。すると、i番目の生き物が他のすべての生き物と合体するためには、0<=i<=n-2について(0から始まるインデックス基準）、(i番目の累積和)*2 >= (i+1番目の生物の大きさ）を満たしている必要がある。逆に言うと、これを満たさない生物iがあった場合、それ以下の生物も同様に条件をみたすことができない。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

int main() {
    ll n;
    cin >> n;
    vector<ll> a(n);
    for(int i=0;i<n;i++) cin >> a[i];
    sort(a.begin(), a.end());
    vector<ll> sum(n);
    for(int i=0;i<n;i++) {
        if(i==0) sum[i] = a[i];
        else {
            sum[i] = sum[i-1] + a[i];
        }
    }
    int ans=n;
    for(int i = n-2;i>=0;i--) {
        if(sum[i] * 2 < a[i+1]) {
            ans -= (i + 1);
            break;
        }
    }
    cout << ans << endl;

}