SRM608 Div1 Easy "MysticAndCandies"

問題

TopCoder Statistics - Problem Statement

訳

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

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

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

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

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

制約

1 <= 箱の数 <= 50
1 <= low[i], high[i] <= 10^7

考えたこと

①...Div2の簡単版と同じようにやる。ただし、こちらはlowで最小についての情報が追加されているので、high[i]について、他のlowの合計値をCから引いたものremがhigh[i]よりも小さければ、highをremで更新しておく。

②...lowを大きい順に並べておきて、順番に足していってXを超えた時の箱の数を数える

答え = min(①, ②)

ソースコード

class MysticAndCandies {

    public:

    int minBoxes(int C, int X, vector <int> low, vector <int> high) {

        int all = 0;
        int N = low.size();

        for (int i = 0; i < N; i++){
            all += low[i];
        }

        // ①
        // highを更新
        for (int i = 0; i < N; i++){
            int rem = C - (all - low[i]);
            high[i] = min(rem, high[i]);
        }

        // Div2のやつと同じようにやる
        sort(high.begin(), high.end());

        int rem = C - X;
        int cnt1 = N;
        for (int i = 0; i < N; i++){
            if (rem < high[i]){
                break;
            }
            rem -= high[i];
            cnt1--;
        }

        //②
        sort(low.begin(), low.end(), greater<int>());

        int sum = 0;
        int cnt2 = 0;
        for (int i = 0; i < N; i++){
            if (X <= sum){
                break;
            }
            sum += low[i];
            cnt2++;
        }

        return min(cnt1, cnt2);

    }
};