AtCoderログ：0059 - AGC 027 A

問題

問題文

$N$ 人の子供がいます。 子供たちには $1,2,\ldots,N$ と番号が振られています。
すぬけ君は、$x$ 個のお菓子を子供たちに配ることにしました。 このとき、すぬけ君は $x$ 個のお菓子をすべて配り切らなければなりません。 なお、お菓子を貰わない子供がいても構いません。
各 $i~(1 \le i \le N)$ について、子供 $i$ はちょうど $a_i$ 個のお菓子を貰うと喜びます。すぬけ君は、お菓子を配る方法を工夫し、喜ぶ子供の人数を最大化しようとしています。喜ぶ子供の人数の最大値を求めてください。

制約

・入力はすべて整数である。
・$2 \le N \le 100$
・$1 \le x \le 10^9$
・$1 \le a_i \le 10^9$

収録されている問題セット

• AtCoder に登録したら次にやること [第06問類題]

• AtCoder Problems Boot camp for beginners Easy 100 [#022]

回答

回答1 (AC)

喜ぶ子供の人数を最大になるのは、喜ぶお菓子の個数が少ない子供から順番に配ったときです。処理としては、喜ぶお菓子の個数を配列 a() に受け取った後、小さい順 (昇順) にソートし、小さい順に配っていけば良いでしょう。お菓子を配って喜んだ子供の人数を child 人(初期値 0)、そのとき残っているお菓子を x 個とすると、次の子供を喜ばせられるかどうかは x >= a.at(child) で判定できます。気をつけないといけないのは最後の子供のときで、最後まで残ったお菓子は最後の子供に全てあげる必要があるので、最後の子供が喜ぶ個数かどうかをチェックする必要が生じます。コードは以下のようになりました。

agc027a-1.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n, x;
  cin >> n >> x;

  vector<int> a(n);
  for ( int i=0; i<n; i++ ) {
    cin >> a.at(i);
  }
 
  sort( a.begin(), a.end() );

  int child = 0;
  while ( x>0 ) {
    if ( x>=a.at(child) && child<n-1 ) {
      x -= a.at(child);
      child += 1;
    } else if ( x==a.at(child) && child==n-1 ) { 
      child += 1;
      break;
    } else {
      break;
    }
  }

  cout << child << endl;
}

調べたこと

AtCoder の解説 → コンテスト全体の解説

回答1と同じ方針でした。

リンク

前後の記事

• 前の記事 → AtCoderログ：0058 - ABC 139 B