ABC 401-500/ABC455C - Vanish - 競技プログラミング用 知識集積所

---

問題

ABC455C

必要知識

B以下レベルの内容は省略

• 貪欲法（アルゴリズム系）※

考え方

xを初めて選んだ時、xの個数がm個あれば、合計はm*xだけ減少する。
この減少値が最大であるものを常に選んでいく貪欲法※が成立する。

というのは、K回の操作のうち1回目に減少値最大であるx以外の何かが選ばれているとすると、

• 2回目以降でxが選ばれるなら、順番を入れ替えて先頭をxにしたものと同等である
• 2回目以降でxが選ばれないなら、1回目をxに差し替えたものより悪い結果にしかならない

と、いずれでも1回目がxである別の選択と同等以下であるため。
これを繰り返し適用すると、任意の回で今の最大減少を貪欲に選ぶのが最善ということになる。

さて、では最大減少をどのように考えるか。
まず、各数を初めて選んだ時の減少値であるが、
もしAの最大値が10^5などであれば、その長さをもつvectorを用意して、Aを前から順に見て求めることができる。
が、今回は最大2*10^9であるため、メモリや時間が足らなくなる。
そこで、登場しない数は0であるということを活かしてmap※で管理することで、登場する数値のみ情報を用意すればいいため、間に合うようになる。
登場する全ての数値について減少値を求めたら、それらをpriority_queue※にでも入れてしまえばよい。

減少量が大きい方からK個（なくなったらそこまで）を捨て、残りを合計すれば答え。

解答例

解答例

注意点

long long型を使用する。

Aの値をたくさん足すので、int型からはみ出る。
答えはもちろん、減少量についてもlong long型を用いること。

別解