Codeforces Round #515 (Div. 3)D. Boxes Packing
問題概要
大きさ の箱が
個あり, これに
個の荷物を詰め込んでいく.
番目の荷物の大きさは
である.
箱詰めは以下のアルゴリズムにより進行する.
- まず, 空箱を手に取る
- 残っている荷物の中で番号が最も小さい荷物を箱に入れようと試みる. もし箱の残り容量が荷物の容量を切っていた場合, 新しい箱をとりだしそれに荷物をいれる. どちらにせよ, 残り容量は荷物の容量分だけ減少する.
個以内の箱で全ての荷物を入れきれることができたらパッキング成功, できなければパッキング失敗である.
箱に荷物を詰め込む前に, 荷物を小さいものから任意の個数捨てることができる. 最大何個の荷物を箱詰めできるか？（パッキング成功はしなければならない）
制約
解法
二分探索やるだけです. おそらく diff が高いのは誤読でしょう.
個捨てたときにパッキング成功できるか？という判定問題を考えれば, これは
に対して単調性があり, また判定は線形でできるので, 二分探索は正しく動作します.
