CodeForces #375_Div2 : C. Polycarp at the Radio

Problem - C - Codeforces

問題

大きさ の整数配列 が与えられる。
「の値を任意の値に変更することができる」 という条件下で、
から それぞれの値の出現数の最小値を最大化させたい。

最大化させた出現数の最小値 / この時の最小変更回数 / 変更後の配列 を求めよ。

解法

まず第一に配列の大きさ 、最大化させたい値の範囲 から 、
最大化させた出現数は に固定される。 ( とおく)

( を超える値の数の総数) + (から の中で出現数がを超えた差分) を使って
〜 の内、出現数がに達していないものを補填してあげれば良い。

〜 の出現数を配列 、
( を超える値の数の総数) を ]、
(から の中で出現数がを超えた差分) を ]〜] に入れ管理している。

計算量は

ソース

感想

やるだけの問題なのに落としたのが勿体なさすぎる・・