📝 题目大意

给定 $N$ 个球，每个球上写有一个整数 $A_i$。可以修改任意球上的整数，目标使所有球上整数的种类数不超过 $K$。求最少需要修改多少个球。

💡 解题思路

1. 题目分析：题目本质是"保留不超过 $K$ 种数字，把其余数字的球全部改掉"。修改一个球时，可以将其改为任意值（包括已有的 $K$ 种之一），因此修改代价就是该球所属数字种类的出现次数。要使修改次数最少，应该保留出现次数最多的 $K$ 种数字，把其余数字对应的球全部改掉。

2. 算法推导：

   • 首先统计每种数字的出现次数（频率）。由于 $1 \leq A_i \leq N$，可以直接用大小为 $N$ 的数组 a 作为桶，a[x] 表示数字 $x$ 的出现次数。
   • 将频率数组按从大到小排序（sort(a.rbegin(), a.rend())）。
   • 排序后，前 $K$ 个元素就是出现次数最多的 $K$ 种数字的频率，应保留不动。
   • 从第 $K$ 个位置开始（下标 $K$），所有后续元素的频率之和即为需要修改的球数——因为这些数字种类要么被淘汰，要么从未出现（频率为 $0$，累加也不影响结果）。
   • 最终答案 ans = sum(a[K] ... a[N-1])。

3. 边界与细节：

   • 当 $K \geq$ 实际不同数字种类数时，无需修改任何球，答案为 $0$。此时从 $K$ 开始累加的全是 $0$，算法自然得出 $0$，无需特判。
   • 输入中的 $A_i$ 范围是 $1 \sim N$，而桶数组索引从 $0$ 开始，因此代码中 b-- 将值映射到 $[0, N-1]$。
   • 桶数组大小设为 $N$ 足够覆盖所有可能值（因为 $A_i \leq N$）。
   • $N$ 最大 $2 \times 10^5$，答案不会超过 $N$，用 int 即可。

⏱️ 复杂度分析

• 时间复杂度：统计频率遍历 $N$ 个输入，$O(N)$；排序频率数组，$O(N \log N)$；累加求和，$O(N)$。总体 $O(N \log N)$。
• 空间复杂度：频率数组 a 大小为 $N$，$O(N)$。

💻 标准代码 (C++)

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, k; 
    cin >> n >> k;
    // a[i] 表示数字 i（0-indexed）的出现次数，大小设为 n 足够
    vector<int> a(n, 0);
    for(int i = 0; i < n; i++){
        int b; 
        cin >> b;
        b--;          // 将 1-indexed 转为 0-indexed
        a[b]++;       // 统计每种数字的出现次数
    }
    // 按频率从大到小排序
    sort(a.rbegin(), a.rend());
    int ans = 0;
    // 保留前 K 个最频繁的数字，从第 K 个开始的所有频率之和即为需要修改的球数
    for(int i = k; i < n; i++) ans += a[i];
    cout << ans << endl;
    return 0;
}