典型探索問題を解く

問題の解法が浮かばないなら、とりあえず解法の全探索をすればいいと思った。

パラメータそれぞれに注目して解けるか考える。
DPなら、テーブルに何を持つかを全通り考えてみる。

数字がn個与えられる。それをk個のグループに分ける。
グループの数字の総和の最大値が最小となるように分ける。

なんか二分探索っぽいキーワードが。

1 ≤ n ≤ 100,000
1 ≤ k ≤ 100,000
1 ≤ w_i ≤ 10,000

i番目までの荷物をいれたときの最大値を求めていく、と考えて無理そうなので諦める。
これだと、どの数字をどのグループに入れたかも保持しないとできない。その上遷移もできなさそう。

グループの数変えても仕方ない。

総和の最大値がi以下のとき、グループにできる数字の個数、と考える。
iが大きければ、貪欲にグループを作れば良い。
→総和の最大値を全通り試してグループができるか調べればよい。
　→二分探索でいけそう。
　　→できた。