Donus2015 D.ドーナツの箱詰め
問題
K個のドーナツをN個の箱に詰めたい。箱は1つのドーナツをいれることができる。
箱のサイズが小さい箱があれば、大きい箱の中に入れる、ような入れ子にできるが、サイズの差分だけの緩衝剤を入れる必要がある。
必要な緩衝剤の合計の最小値を求める。
また、Q個の箱indexが順に与えられるので、その箱までをつぶした場合のそれぞれの緩衝剤の合計の最小値に答える。
1<=K<=N<=2*10^5
箱のサイズ<=2*10^5
0<=Q<=N-K
考え方
問題を考察すると、箱のサイズをソートして差分を取ったもので小さいものからN-K個取り出すタスクになる。問題は、
①「箱のサイズをソートしたもの」から該当の箱を見つけて、その1つ大きい箱と小さい箱のサイズを高速に見つけて、そのあと削除したい
②削除後の「箱のサイズをソートしたもの」と「ソートしたものの差分」を高速に再構築したい
③差分からN-K個を取り出したときの合計値を高速に求めたい
になる。
①は、すべての箱サイズが異なることからi番目の箱のサイズがxであれば、箱のサイズをset
②の「箱のサイズをソートしたもの」は上記でsetを使うので問題ない。
②の「ソートしたものの差分」と③のN-K個(top-k)の合計値を高速に求めたい。
「ソートしたものの差分」は、何が何個あるか？だけを保持すればよく、合計値のtop-kを求めるためにSegmentTreeが使える。
各葉ノードは、差分の値を表し、各ノードは「自ノード以下の部分木の個数と合計値」を持たせて上げればよい。
削除操作は、両端の場合は削除のみ。そうでなければ両隣を削除し、両隣の差分を追加。
