TopCoder SRM608: MysticAndCandiesEasy

箱の全集合を \( S \) 、選んだ箱の集合を \( A \)とする。

選んだ箱の集合に含まれるキャンディが最小となる場合というのは、選ばれなかった箱に可能な限りキャンディが入っている場合と同等になる。

よって \(A\) に含まれるキャンディの最小値は、\(C - \sum_{i \in S\setminus{A}} high[i] \) に等しい。この式から、最大値の値が少ないものを選ばないことで、キャンディの最小値が上がることがわかる。よって全ての箱を選んでいる状態から、単にループ処理で小さい順に箱を除外していけばよい。

public class MysticAndCandiesEasy {
    public int minBoxes(int C, int X, int[] high) {
        Array.Sort(high);
        int sum = 0;
        int n = high.Length;
        for (int i = 0; i < high.Length; i++) {
            sum += high[i];
            if (C - sum < X) return n - i;
        }
        return 0;
    }
}