HJ123 预知

知识点数论

校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述

牌桌上有 nn 种不同的卡牌，第 ii 种卡牌有 aiai​ 张。初始时，所有的卡牌均背面朝上，但不知道其确切的种类。你有两次翻牌机会，翻牌后，如果两张卡牌种类一致，那你就输了。两次翻牌同时进行（不存在根据翻开的第一张牌更改策略的情况）。

你不喜欢运气游戏，所以你可以通过手段随机预知 kk 张卡牌后再进行游玩。

然而，预知很累！你想要知道，你至少需要预知多少张卡牌，才能保证你不会输。

输入描述：

每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≦T≦2×105)T(1≦T≦2×105) 代表数据组数，每组测试数据描述如下：

第一行输入一个整数 n(1≦n≦2×105)n(1≦n≦2×105) 代表卡牌种类数。
第二行输入 nn 个整数 a1,a2,…,an(1≦ai≦109)a1​,a2​,…,an​(1≦ai​≦109) 代表每种卡牌数量。

除此之外，保证每一组测试数据的卡牌总数之和不小于 22 ；单个测试文件的 nn 之和不超过 2×1052×105 。

输出描述：

对于每一组测试数据，如果没有必胜策略，直接输出 −1−1 ；否则，在单独的一行上输出一个整数，代表你至少需要预知多少张卡牌，才能保证你不会输。

示例1

输入：

3 2 1 1 1 10 2 2 3

复制输出：

0 -1 3

复制说明：

对于第一组测试数据，只有两张卡牌，且各不相同，直接翻开即可。 对于第二组测试数据，由于卡牌种类唯一，不管怎么翻都会输。

#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 10; int a[N]; void solve() { int n; cin >> n; for (int i = 1; i <= n; i ++ ) cin >> a[i]; if (n == 1) { cout << -1 << endl; return ; } int mx = -1; for (int i = 1; i <= n; i ++){ mx = max(mx, a[i]); } if (mx == 1) cout << 0 << endl; else { int cnt = 0; for (int i = 1; i <= n; i ++ ) { if (a[i] > 1) cnt ++; } if (cnt == 1) cout << mx - 1 << endl; else cout << mx << endl; } } int main(){ int T; cin >> T; while (T -- ) solve(); return 0; }