题解 | 预知

思路：

从全集S中随机选取p个元素后，形成了两个集合。

S1：选取的已知的p个元素

S2：剩下未知的元素

如何根据S1和S2做出必胜的判断——即一定不会抽到两个相同元素？

1、要求S1的元素包含至少两种不同的类或者某个类的全部元素。根据鸽巢原理可得p1=max(占比最大的类的元素的个数）

2、要求S2包含每个类的元素恰为一个，共有k个元素。这里要求p2=|S|-k

选取以上的两个数的最小值：min(p1,p2)即可。

#include <iostream>
using namespace std;

int check() {
    int n;
    cin >> n;
    long tmp;
    long nmax = 0;
    long size = 0;
    if (n == 1)    {
        cin >> tmp;
        return -1;
    }
    for (int i = 0; i < n; i++) {
        cin >> tmp;
        size += tmp;
        nmax = max(nmax, tmp);
    }

    if (nmax == 1) return 0;//这里可以注释掉
    return min(nmax, size - n);
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cout << check() << '\n';
    }
}
// 64 位输出请用 printf("%lld")