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