けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 027 A - Candy Distribution Again (200 点)

ちょっと注意。ABC なら 300 点かな。

問題へのリンク

問題概要

 N 人がいて、キャンディ  x 個を余らさずに  N 人に分配する。 i 人目の人はちょうど  a_i 個のキャンディを受け取ると喜ぶ。喜ぶ人数の最大値を求めよ。

制約

  •  2 \le N \le 100

考えたこと

基本的には  a_i が小さい方から配っていけばよい。そうすればより多くの人を喜ばせることができる。

しかし、 N 人目だけ注意である。 x a_N よりも大きかったら、 N 人目を喜ばせることはできない。この場合の答えは  N-1 になる。

もとより答えが  N になる場合というのは、 x がちょうどぴったり  a_i の総和になっている場合のみにかぎられる。

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

int main() {
    int N; cin >> N;
    long long x; cin >> x;
    vector<long long> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    sort(a.begin(), a.end());
    int res = 0;
    for (int i = 0; i < N; ++i) {
        if (x >= a[i]) ++res, x -= a[i];
        else break;
    }
    if (res == N && x) --res;
    cout << res << endl;
}