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

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

問題へのリンク

問題概要

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

制約

• 

考えたこと

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

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

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

#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;
}