典型探索問題を解く
問題の解法が浮かばないなら、とりあえず解法の全探索をすればいいと思った。
パラメータそれぞれに注目して解けるか考える。 DPなら、テーブルに何を持つかを全通り考えてみる。
AOJ ALDS1_4-D Search - Allocation
問題概要
数字がn個与えられる。それをk個のグループに分ける。 グループの数字の総和の最大値が最小となるように分ける。
なんか二分探索っぽいキーワードが。
制約
1 ≤ n ≤ 100,000
1 ≤ k ≤ 100,000
1 ≤ w_i ≤ 10,000
考え方
- nに注目
i番目までの荷物をいれたときの最大値を求めていく、と考えて無理そうなので諦める。 これだと、どの数字をどのグループに入れたかも保持しないとできない。その上遷移もできなさそう。
- kに注目
グループの数変えても仕方ない。
- 総和の最大値に注目
総和の最大値がi以下のとき、グループにできる数字の個数、と考える。
iが大きければ、貪欲にグループを作れば良い。
→総和の最大値を全通り試してグループができるか調べればよい。
→二分探索でいけそう。
→できた。