これを自力ACしました。バチャ中はEに引っかかってここまでたどり着けなかったけど、先にFを見ておくべきでした...。
問題概要
数列 が与えられる。以下の操作を繰り返して
内に少なくとも
個の等しい要素を取得しなさい。
内の最大の要素の大きさを 1 小さくする。
解説
まず をソートする。
個出現させる要素の大きさは最初
に入っている要素の大きさと必ず一致するので、何を
個得るかを全探索する。
を
個得るときにかかるコストは 1.
以下を全てインクリメント、2.
以上を全てデクリメント、3. 両方するの 3 通りが考えられる。それぞれのコストは
によって求められ、答えはこれらの最小値である。
総和の部分はあらかじめ累積和を求めておくと で求められるため、時間計算量はソートにより
となる。
