Submission #2120438

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;

/*
<url:https://agc011.contest.atcoder.jp/tasks/agc011_b>
問題文============================================================
 すぬけ君は，N 匹の変わった生き物を見つけました．
 それぞれの生き物には色と大きさが定まっており，i 番目の生き物の色は i，大きさは Ai で表されます．
 
 どの生き物も，大きさが自分の 2 倍以下であるような他の生き物を吸収することができます．
 大きさ A，色 B の生き物が大きさ C，色 D の生き物を吸収すると (C≤2×A)，合体して大きさ A+C，
 色 B の生き物になります．
 ここで，2 匹の生き物の大きさによっては，どちらも他方を吸収することが可能な場合があります．
 
 すぬけ君がこの生き物たちを観察していると，合体を繰り返して，最終的に 1 匹になりました．
 このとき，残った生き物の色として考えられるものは何種類あるかを求めてください．
=================================================================

解説=============================================================

 N匹のサイズを昇順に並べた時
     i番目の生き物がi+1番目の生き物を食べることができるには
     i+1番目の生き物のサイズ <= 1...i までのサイズの合計*2
     であれば良い
 
 よって累積和で1..iまでの総和を求めておき,大きい順に見ていった時何匹連続して
 上の式を満たすかどうかで判断すれば良い
================================================================
*/
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    ll N; cin >> N;
    vector<ll> A(N);
    for(auto &in:A) cin >> in;
    sort(A.begin(),A.end());
    vector<ll> cusum(N+1,0);
    for(int i = 0; i < N;i++) cusum[i+1] = cusum[i] + A[i];
    ll ans = 0;
    A[0] = LINF;
    for(ll i = N - 1; i >= 0; i--){
       if(A[i] <= 2*cusum[i]) continue;
        ans = N - i;
        break;
    }
    cout << ans << endl;
	return 0;
}

Submission Info

Judge Result