CF1966A Card Exchange 题解

题目链接：Card Exchange

题意：

你有 \(n\) 张卡片，每张卡片写着一个数 \(a_i\) 。

给定一个正整数 \(k\) ，定义一次操作为，选 \(k\) 张数字相同的卡片，

然后把他们替换成 \(k-1\) 张任意数字的卡片，这 \(k-1\) 张上写的可以互不相同。

问最少可以持有多少张卡片。（下图是 \(k=3\) 的例子）

输入格式：

\(t (1\le t \le 500)\) 组数据

每组给出第一行 \(n,k(1 \le n \le 100,2\le k \le 100)\) ，第二行给出 \(a_i(1\le a_i \le 100)\)​ 。

输出格式：

对于每组数据，输出答案。

容易发现，只要有一种卡牌的数量超过 \(k\) ，答案就是 \(k-1\) ，否则一定是 \(n\) 。

因为我们可以把超过 \(k\) 张的那种卡片转换成相同的其他数字的卡片，进而消灭那种数字的多余牌数。

时间复杂度 \(\mathcal{O}(tn)\) ，空间复杂度 \(\mathcal{O}(V=\max a_i)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(666))

int a[N], c[N];
void clear()
{
    memset(c, 0, sizeof(c));
}
void solve()
{
    clear(); int n, k; cin >> n >> k;
    for(int i = 1; i <= n; i++) { cin >> a[i], ++c[a[i]]; }
    for(int i = 1; i <= n; i++) {
        if(c[a[i]] >= k) { cout << k - 1 << '\n'; return; }
    }
    cout << n << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}