E - Insert or Swap
Darjeeling
2
s
1024
MB
500
点
問題文
$N$ 個のボールと空の箱があります。
ボールには、それぞれ $1, 2, ... , N$ と番号が付けられており、番号 $i$ のボールには非負整数 $A_i$ が書かれています。
あなたはこれから、$i=1,2,...,N$の順に以下の操作のうちいずれかを行います。
操作 1：番号 $i$ のボールを箱に入れる。番号 $i$ のボールを箱に入れる前に既に箱に入っているボールの数が $x$ 個であった時、コストは $x$ かかる。
操作 2：箱に入っているボールを1つ選び、そのボールを捨てる。その後、番号 $i$ のボールを箱に入れる。操作をする前に箱に入っているボールの個数が $x$、捨てたボールに書かれている整数が $y$ であった時、コストは $x+y$ かかる。なお、この操作は箱にボールが 1 つ以上ある時しか行うことが出来ない。
最終的に箱に入っているボールの数を $K$ 個にしたい時、かかるコストの合計の最小値を求めてください。
制約
- $1 \leq K \leq N \leq 2 \times 10^5$
- $0 \leq A_i \leq 10^9$
- 入力は全て整数
入力
$N$ $K$
$A_1 \space A_2 \space \ldots \space A_N$
出力
答えを1行に出力してください。
入力例 1
5 3
3 1 4 1 5
出力例 1
9
以下のように操作をするのが最適です。
- 操作 1 を行い、箱に番号 $1$ のボールを入れる。操作を行う前の箱は空なので、コストは $0$ かかる。
- 操作 2 を行い、番号 $1$ のボールを捨てて番号 $2$ のボールを箱に入れる。操作を行う前の箱にはボールが 1 個入っていて、捨てた番号 $1$ のボールには非負整数 $3$ が書かれているので、コストは $1+3=4$ かかる。
- 操作 2 を行い、番号 $2$ のボールを捨てて番号 $3$ のボールを箱に入れる。操作を行う前の箱にはボールが 1 個入っていて、捨てた番号 $2$ のボールには非負整数 $1$ が書かれているので、コストは $1+1=2$ かかる。
- 操作 1 を行い、箱に番号 $4$ のボールを入れる。操作を行う前の箱にはボールが 1 個入っているので、コストは $1$ かかる。
- 操作 1 を行い、箱に番号 $5$ のボールを入れる。操作を行う前の箱にはボールが 2 個入っているので、コストは $2$ かかる。
以上の操作を行った後の箱の中には番号 $3,4,5$ のボールが入っており、箱の中のボールの個数は $K=3$ 個になっています。
またこの時、コストの合計は $0+4+2+1+2=9$ です。コストが $9$ 未満になるような操作の仕方は存在しないため、答えとして $9$ を出力します。
入力例 2
4 1
1 10 100 1000
出力例 2
114