Mister雑記

競プロやります。

AGC027-A 「Candy Distribution Again」 (200)

細かい勘違いに要注意。

問題リンク

概要

 N人の子どもがいて、 i番目の子はちょうど a_i個の飴を貰うと喜ぶ。

あなたは今 x個の飴を持っていて、これを N人の子どもに全て配らなければならない。このとき喜ぶ子どもの人数の最大値を求めよ。

制約

  •  2 \leq N \leq 100
  •  1 \leq x \leq 10^9
  •  1 \leq a_i \leq 10^9

解説

わざわざ要求個数の多い子に飴を配るよりは、要求個数の少ない子をできるだけ多く喜ばせる方が得なのは明らかだろう。ということで、 aを昇順にソートして、貪欲に配っていくのが最善となる。

あと問題となるのは、「飴を全て配らないといけない」という制約。最後の子まで適切に飴を配ることができても、飴が余っていると残念ながらアウトとなる。 このときある程度の被害が出るわけだが、これを最小化するには誰か一人に余った飴を押し付ければいい。

実装例

#include <algorithm>
#include <iostream>

using namespace std;

int main() {
    int N, x;
    cin >> N >> x;
    int a[N];
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }

    sort(a, a + N);
    int ans = 0;

    // 少ない子から順に飴を配る
    for (int i = 0; i < N; ++i) {
        if (x >= a[i]) {
            ++ans;
            x -= a[i];
        }
    }

    // 飴が余っていたら1人を犠牲にする
    if (ans == N && x > 0) --ans;

    cout << ans << endl;
    return 0;
}

感想

  • 子どもにひどいことしないで。