A
很简单的题，就过了
B
题意：
给定一个长度为 \(n\) 的数组 \(A\)，你可以将其重新排序，并得到一个新数组 \(B = [a_1 + a_2, a_2 + a_3, ..., a_{n-1} + a_n]\) ，使得
\(mex(B)\) 最小，\(mex\) 为在 \(B\) 中找到一个最小的 \(B\) 中不含有的正整数， 题目有多组测试数据
思路：
容易发现答案会很小，因为两个数相加，太容易产生数与数之间的间隔了。顺着这个想法我们继续思考。
- 若 \(0\) 的个数小于等于一半， 我们将 “0” 和别的数间隔放置， 如 “0，11，0，12”，则可使答案最优，为 “0”。
- 若 \(0\) 的个数大于一半，我们无法得到答案是 “0”，那么索性把 “0”全部放在最前面。这样不影响答案。
- 若上述情况下我们有一个比 \(1\) 大的数，那么我们就可以把这个数夹在 “0” 和 “1” 之间，如 “0，0，0，9，1”，此时答案为 “1”。
- 如果我们并没有这个“鸿沟”，我们只有半数以上的 “0” 和剩余的 “1”，我们也不难构造出答案为 “2”。
综上，答案仅在 \(0, 1, 2\) 中取得。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int T, n;
int main(){
cin >> T;
while(T --){
scanf("%d", &n);
int cnt1 = 0, cnt0 = 0;
for(int i = 1; i <= n; i++){
int t; scanf("%d", &t);
if(!t) cnt0 ++;
if(t == 1) cnt1 ++;
}
if(cnt0 <= (n + 1) / 2) puts("0");
else {
if(n - cnt1 - cnt0 > 0) puts("1");
else if(cnt1) puts("2");
else puts("1");
}
}
return 0;
}
/*
1 0 1 0 1 0
0 1 0 1 0
0 0 0 0 9 1
0 0 0 0 1 1
*/