SRM608 Div2 Medium "MysticAndCandiesEasy"

問題

TopCoder Statistics - Problem Statement

訳

トップコーダーの管理者であるmystic_tcはテーブルの前で座っている。彼はテーブルにキャンディの箱がN個置かれているのを見つけた。

彼はそれぞれの箱にいくつのキャンディが入っているのか、正確なことは分かっていない。しかし、下記のような事が分かっている。

・キャンディは全部でC個ある。
・i番目の箱には0～high[i]個の範囲で、キャンディが入っている。

mystic_tcは、次のようにキャンディを食べる。最初、彼は複数の箱を適当に選び、それから箱を開け、中に入っているキャンディをすべて食べる。彼は少なくともX個のキャンディを食べたいと思っている。そして彼は、合計すると必ずキャンディの数がX個以上になるように箱を選ぶ。

あなたはint CとX、そしてint[] highが与えられる。mystic_tcが選ぶ箱の、最小の個数を返せ。

制約

1 <= highの要素数 <= 50
1 <= high[i] <= 50
1 <= C <= high[i]の合計
1 <= X <= C

考えたこと

i番目の箱を選ばなくても、キャンディの数がX個を超えるには、その箱に入っているキャンディの最大数をCから引いた時に、X個以上となっていればよい。（X <= C - high[i]）さらにそこからj番目の箱を選ばなくても、キャンディの数がX個を超えるには、その箱に入っているキャンディの最大数を、残っているキャンディから引いたときに、X個以上となっていればよい。（X <= C - high[i] - high[j]）

ということで、highを昇順に並べて順々にキャンディを取り除いていき、X個以上となるギリギリのラインを見てあげれば、最適となる。

ソースコード

class MysticAndCandiesEasy {

    public:

    int minBoxes(int C, int X, vector <int> high) {
        sort(high.begin(), high.end());
        
        int res = high.size();
        int rem = C;
        for (int i = 0; i < high.size(); i++){
            rem -= high[i];
            if (rem < X) break;
            res--;
        }
        cout << endl;
        return res;
    }
};