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); } };