给一个长为 \(n\) 的数组 \(a\) ，定义 \(a\) 的 \(score\) 为 \(a_1+ a_2, a_2 + a_3, \cdots, a_{n - 1} + a_n\) 的 \(MEX\) 。
找到 \(a\) 的 最小 \(score\) 如果 \(a\) 可以被重排。\((0 \leq a_i \leq 2 \times 10^5)\) 。
\(MEX\) 即最小排除数，即一个集合的补集的最小值。
典：\(MEX\) 问题可以出得很复杂，但思维的角度通常都是从最小值考虑。
显然的 \(MEX\) 贪心：
要求 \(a_1+ a_2, a_2 + a_3, \cdots, a_{n - 1} + a_n\) 的 \(MEX\) 最小，显然从 \(0\) 开始递增考虑，构造这个数不出现。一定只需要考虑有限个数即可停止，或找到通项。
逐步分析构造法：
-
构造 \(0\) 不出现：
- 观察到 \(0\) 加上任何一个正整数都会 \(> 0\) ，只需要让正整数把 \(0\) 隔开即可构造 \(0\) 不出现。
- 若 \(cnt0 \leq \lceil \frac{n}{2} \rceil\) ，则 \(MEX = 0\) 。
-
构造 \(1\) 不出现：
- 若 \(cnt0 > \lceil \frac{n}{2} \rceil\) ， \(0\) 一定出现，此时需要构造 \(1\) 不出现。
- 当有正整数存在，即 \(n - cnt0 > 0\) 。只要 \(1\) 不和 \(0\) 相邻，则加上任何一个相邻数都会 \(\geq 2\) 。
- 存在 \(> 1\) 的数将所有 \(1\) 和 \(0\) 隔开即可构造 \(1\) 不出现。 \(n - cnt0 > cnt1\) ， \(MEX = 1\) 。
- 否则 \(1\) 一定出现， \(n - cnt0 = cnt1\) ， \(MEX = 2\) 。
- 当没有正整数存在，即 \(n - cnt0 = 0\) ，则此时 \(MEX = 1\) 。
- 当有正整数存在，即 \(n - cnt0 > 0\) 。只要 \(1\) 不和 \(0\) 相邻，则加上任何一个相邻数都会 \(\geq 2\) 。
- 若 \(cnt0 > \lceil \frac{n}{2} \rceil\) ， \(0\) 一定出现，此时需要构造 \(1\) 不出现。
-
当无法构造 \(1\) 不出现，此时正整数都为 \(1\) 且 \(cnt0 > \lceil \frac{n}{2} \rceil\) ，一定可以构造 \(2\) 不出现，\(MEX = 2\) 。不再有其他情况。
view
#include <bits/stdc++.h>
void solve() {
int n; std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; i++) std::cin >> a[i];
int cnt0 = std::count(a.begin(), a.end(), 0), cnt1 = std::count(a.begin(), a.end(), 1);;
if (cnt0 <= (n + 1) / 2) std::cout << 0 << '\n';
else if (cnt0 < n) {
if (n - cnt0 > cnt1) std::cout << 1 << '\n';
else std::cout << 2 << '\n';
}
else if (cnt0 == n) std::cout << 1 << '\n';
else std::cout << 2 << '\n';
}
int main() {
int _ = 1; std::cin >> _;
while (_--) { solve(); }
return 0;
}