C_

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)$

代码：

cpp

#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;
}