[R29B]最少修改 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的数组 $A$ 和一个整数 $k$。

你可以进行如下操作任意次：

• 选择数组中的一个元素 $A_i$，并将其修改为任意其他整数。

求最少的操作次数使得修改后的数组中，任何一个数字的出现次数都不超过 $k$。

请计算并输出最少的操作次数。

格式

输入格式

第一行包含 $2$ 个整数 $n, k$。具体意义见题目描述。

第二行包含 $n$ 个整数，表示数组 $A$ 的元素 $A_1, A_2, \ldots, A_n$。

输出格式

输出一个整数，表示最少的操作次数。

样例

样例输入 #1

7 2
1 1 2 3 1 2 1

样例输出 #1

2

样例解释 #1

第一次操作：将 $A_1$ 修改成 $5$。此时数组为 $[5,1,2,4,1,2,1]$。

第二次操作：将 $A_2$ 修改成 $4$。此时数组为 $[5,4,2,4,1,2,1]$。

此时所有数字的出现个数均不超过 $2$。

可以证明，不存在比 $2$ 更小的操作方式满足条件。

数据规模

对于 $100\%$ 的数据，$1 \leq k \leq n \leq 10^5$，$1 \leq A_i \leq 10^5$。