卡牌交换 详细题解

核心结论（标程核心思想）

1. 若初始手牌中不存在任意一个数字出现次数 $\ge k$，则无法执行任何操作，答案为初始卡牌数 $n$；
2. 若初始手牌中存在任意一个数字出现次数 $\ge k$，则一定可以通过操作将卡牌数量减少到 $k-1$，且 $k-1$ 是理论最小值，无法更小。

一、题目规则回顾

我们可以执行任意次操作：

• 选择手中**$k$ 张数字相同**的卡牌；
• 将这 $k$ 张卡牌交换为 $k-1$ 张任意数字的卡牌。

每次操作后，卡牌总数恰好减少 $1$（$k \to k-1$）。

二、关键逻辑推导

1. 无法操作的情况

如果所有数字的出现次数都小于 $k$，我们没有任何 $k$ 张相同数字的卡牌可以选择，因此不能执行任何操作。 此时剩余卡牌数就是初始的 $n$。

2. 可以操作的情况

只要有至少一个数字出现次数 $\ge k$，我们就能通过策略不断操作，最终把卡牌数降到 $k-1$。

为什么能降到 $k-1$？（标程算法）

1. 第一步：任选一个出现次数 $\ge k$ 的数字，消耗掉 $k$ 张该数字的卡牌，替换为 $k-1$ 张任意数字的卡牌； 2. 第二步：如果此时还有剩余卡牌，任选一个现存数字 $x$，把新生成的 $k-1$ 张卡牌都设为 $x$； 3. 第三步：此时 $x$ 的出现次数一定会再次 $\ge k$，回到第一步重复操作。

每次操作卡牌总数减 $1$，过程一定会终止，最终能稳定得到 $k-1$ 张卡牌。

为什么 $k-1$ 是最小值？（理论证明）

• 每次操作只能减少 $1$ 张卡牌；
• 当卡牌数 $<k$ 时，无法选出 $k$ 张相同数字的卡牌，也就不能再执行任何操作；
• 因此能达到的最小数量就是 $k-1$，这是最优解。

三、完整解题步骤

对于每组测试用例：

1. 统计所有数字的出现次数；
2. 检查是否存在出现次数 $\ge k$ 的数字：
   • 存在 $\to$ 答案为 $k-1$；
   • 不存在 $\to$ 答案为 $n$。

四、C++ 代码实现（对标标程，复杂度 $O(n)$）

#include <iostream>
#include <cstring>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        // 统计数字出现次数（ci<=100）
        int cnt[105] = {0};
        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            cnt[x]++;
        }
        
        bool ok = false;
        // 检查是否有数字出现次数 >=k
        for (int i = 1; i <= 100; ++i) {
            if (cnt[i] >= k) {
                ok = true;
                break;
            }
        }
        
        if (ok) cout << k - 1 << endl;
        else cout << n << endl;
    }
    return 0;
}

五、样例输入逐组验证

完全匹配题目样例输出！

六、复杂度分析

• 时间复杂度：$O(n)$（仅统计次数+一次遍历检查）；
• 空间复杂度：$O(1)$（固定大小的计数数组）。

总结

1. 核心判断：是否有数字出现次数 $\ge k$；
2. 满足条件 $\to$ 最小剩余卡牌数为 $k-1$；
3. 不满足条件 $\to$ 无法操作，答案为初始卡牌数 $n$。