はまやんはまやんはまやん

hamayanhamayan's blog

Candy Distribution Again [AtCoder Grand Contest 027 A]

https://beta.atcoder.jp/contests/agc027/tasks/agc027_a

解法

https://beta.atcoder.jp/contests/agc027/submissions/3198858

最適分配は喜ぶお菓子の量が少ない子供から分けていくこと。
少ない方から分けていって、ピッタリ渡せる人数が答え。
コーナーケースとして、N人全てに配った場合に手元にお菓子が余ったら、一人に押し付ける必要がある。
なので、答えが1つ減るので注意。

int N, X, A[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> X;
    rep(i, 0, N) cin >> A[i];
    sort(A, A + N);
 
    int ans = 0;
    rep(i, 0, N) {
        if (X < A[i]) break;
        X -= A[i];
        ans++;
    }
    if (0 < X and ans == N) ans--;
    cout << ans << endl;
}