题解

思路

设不同技能值的个数为 $d$，某个技能值的最大出现次数为 $m$。第二队至多选择 $m$ 人，第一队至多选择 $d$ 人，但两队不能使用同一名学生。

做法

若把出现次数最多的技能完全留给第二队，第一队只能使用其余技能，候选答案为 $\min(m,d-1)$。若从该技能中留一人给第一队，第二队至多使用剩余的 $m-1$ 人，候选答案为 $\min(m-1,d)$。两者取最大值。

频率统计得到 $d,m$ 后直接计算上述公式。两个候选分别覆盖第一队是否占用最高频技能，因而包含所有最优方案。

复杂度

每组时间复杂度为 $O(n)$，空间复杂度为 $O(n)$；所有组总时间复杂度为 $O(\sum n)$。

参考实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define endl '\n'
ll rd(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
void solve(){
    int n=rd(),mx=0,d=0;
    vector<int >cnt(n+1);
    rep(i,1,n){
        int x=rd();
        if(!cnt[x]) d++;
        mx=max(mx,++cnt[x]);
    }
    cout<<max(min(mx-1,d),min(mx,d-1))<<endl;
}
int main()
{
    int T=rd();
    while(T--) solve();
    return 0;
}