1194: 单序列敛缩
题目描述
【题目背景】
小 R 在 NOIp 2023 的考场上时，T3 双序列拓展 只获得了 5 分的高分。因此小 R 现在非常讨厌看到「双序列」和「拓展」。
因此，小 W 出了一道 单序列敛缩，以安慰小 R 的心情。
其实题目是小 R 出的（逃
因为初中部 OJ 的公式渲染是依托答辩，建议在 洛谷云剪贴板 中观看题目。
【题目描述】
定义序列 $A={a_1,a_2,\dots,a_i } $ 关于数 $x$ 的「敛缩」操作 $\text{Del}(A, x)$ 为：将 $A$ 中所有 $\ge x$ 的元素减去 $1$。
例如：当 $A={1,1,4,5,1,4}$，$x=4$ 时，进行 $\text{Del}(A,x)$ 后的 $A$ 序列为：
$${1,1,4-1,5-1,1,4-1} ={1,1,3,4,1,3}$$
小 R 给了小 W 一个长度为 $n$ 的正整数序列 $A={a_1,a_2,\dots,a_n}$。小 W 可以花费 $1$ 的代价，任意选择一个整数 $x$，执行 $\text{Del}(A, x)$。
由于小 R 被「双序列拓展」中被复杂的序列整破防了，小 R 希望能得到一个简单的序列。定义一个序列为「简单」的当且仅当序列中有 $\ge k$ 个数相同。
小 W 现在想花费尽量小的代价，让这个序列 $A$ 变成「简单」的。但是他不会做，于是他找到了你，希望你能帮他编程解决这个问题。
输入
第一行，输入两个正整数 $n,k$。
第二行，输入 $n$ 个正整数，表示序列 ${a_1,a_2,\dots,a_n}$。
输出
一行输出一个正整数，表示将 $A$ 序列变为「简单」的所需要的最小代价。
样例输入 复制
6 4
1 1 4 5 1 4样例输出 复制
3提示
【数据范围】
对于 $100%$ 的数据，$1 \le k\le n\le 10^6$，$1\le a_i\le 10^9$。
柳州铁一中学（初中部）第二届程序设计竞赛 G。
by Running_a_way。