AGC027 A - Candy Distribution Again (200点)

問題概要

リンクはこれ

n人の子どもに持っている飴x個を全て配る。
子どもは a[i] 個ちょうどの飴を与えられると喜ぶ。喜ぶ子どもの数を最大化したい。

なお飴をもらわない子どもがいても問題ない。

制約

• 入力はすべて整数である。
• 2 ≤ N ≤100
• 1 ≤ x ≤ 10^9
• 1 ≤ a(i) ≤ 10^9

考えたこと

要はxからa[i]を引くという処理の回数を最大化するということなので整数a[i]が小さければ小さいほど処理の数が増えるのは自明。

よって配列をsortして順にxからa[i]を引いていきcountすればよい。

注意するのは飴を過不足なく配らないといけないということ。不足があればcountせず処理を中断させるようにする。多すぎる場合は最後にxが0以上になるので、countから1を引けばよい。

解答

a.cs

using System;
using System.Linq;

class Program
{
    static void Main(string[] args) {
        int[] s = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int n = s[0];
        int x = s[1];
        int[] a = Console.ReadLine().Split().Select(int.Parse).ToArray();
        Array.Sort(a);
        int count = 0;
        for(int i = 0; i<n; i ++) {
            x -= a[i];
            if (x>=0) count ++;
            else break;
        }
        if (x>0) count --;
        Console.WriteLine(count);
    }
}