MEX Game 1
题面翻译
题目描述
Alice 和 Bob 在大小为 $n$ 的数组 $a$ 上玩一个游戏：Alice 有一个空数组 $c$ 开始。两位玩家轮流进行游戏，Alice 先开始。
在 Alice 的回合中，她从 $a$ 中选择一个元素，将该元素添加到 $c$ 中，然后从 $a$ 中删除该元素。
在 Bob 的回合中，他从 $a$ 中选择一个元素，然后从 $a$ 中删除该元素。
当数组 $a$ 为空时游戏结束。游戏的得分定义为 $c$ 的 MEX $^\dagger$。Alice 希望最大化得分，而 Bob 希望最小化得分。找出如果两位玩家都采取最佳策略时的游戏最终得分。
$^\dagger$ 整数数组的 MEX（最小排除数）定义为不在数组中出现的最小非负整数。例如：
例如：
- $[2,2,1]$ 的 MEX 是 $0$，因为 $0$ 不属于数组。
- $[3,1,0,1]$ 的 MEX 是 $2$，因为 $0$ 和 $1$ 属于数组，但 $2$ 不属于。
- $[0,3,1,2]$ 的 MEX 是 $4$，因为 $0$、$1$、$2$ 和 $3$ 属于数组，但 $4$ 不属于。
输入格式
每个测试包含多个测试用例。第一行包含一个整数 $t$（$1\leq t\leq2\cdot10^4$），表示测试用例的数量。接下来是测试用例的描述。
每个测试用例的第一行包含一个整数 $n$（$1\le n\le2\cdot10^5$）。
每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0\le a_i<n$）。
保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。
样例解释
在第一个测试用例中，得分为 $2$ 的一个可能游戏如下：
- Alice 选择元素 $1$。此时，$a=[0,0,1]$，$c=[1]$。
- Bob 选择元素 $0$。此时，$a=[0,1]$，$c=[1]$。
- Alice 选择元素 $0$。此时，$a=[1]$，$c=[1,0]$。
- Bob 选择元素 $1$。此时，$a=[]$，$c=[1,0]$。
- 最终，$c=[1,0]$，其 MEX 为 $2$。请注意，这只是一个示例游戏，并不一定代表两位玩家的最佳策略。
题目描述
Alice and Bob play yet another game on an array $ a $ of size $ n $ . Alice starts with an empty array $ c $ . Both players take turns playing, with Alice starting first.
On Alice’s turn, she picks one element from $ a $ , appends that element to $ c $ , and then deletes it from $ a $ .
On Bob’s turn, he picks one element from $ a $ , and then deletes it from $ a $ .
The game ends when the array $ a $ is empty. Game’s score is defined to be the MEX $ ^\dagger $ of $ c $ . Alice wants to maximize the score while Bob wants to minimize it. Find game’s final score if both players play optimally.
$ ^\dagger $ The $ \operatorname{MEX} $ (minimum excludant) of an array of integers is defined as the smallest non-negative integer which does not occur in the array. For example:
- The MEX of $ [2,2,1] $ is $ 0 $ , because $ 0 $ does not belong to the array.
- The MEX of $ [3,1,0,1] $ is $ 2 $ , because $ 0 $ and $ 1 $ belong to the array, but $ 2 $ does not.
- The MEX of $ [0,3,1,2] $ is $ 4 $ , because $ 0 $ , $ 1 $ , $ 2 $ and $ 3 $ belong to the array, but $ 4 $ does not.
输入格式
Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 2 \cdot 10^4 $ ) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ).
The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i < n $ ).
It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .
输出格式
For each test case, find game’s score if both players play optimally.
样例 #1
样例输入 #1
3
4
0 0 1 1
4
0 1 2 3
2
1 1
样例输出 #1
2
1
0
提示
In the first test case, a possible game with a score of $ 2 $ is as follows:
- Alice chooses the element $ 1 $ . After this move, $ a=[0,0,1] $ and $ c=[1] $ .
- Bob chooses the element $ 0 $ . After this move, $ a=[0,1] $ and $ c=[1] $ .
- Alice chooses the element $ 0 $ . After this move, $ a=[1] $ and $ c=[1,0] $ .
- Bob chooses the element $ 1 $ . After this move, $ a=[\,] $ and $ c=[1,0] $ .
At the end, $ c=[1,0] $ , which has a MEX of $ 2 $ . Note that this is an example game and does not necessarily represent the optimal strategy for both players.
从0开始找，上限肯定是第一次出现次数为0的数字，在这个数字之前的，看看每一个数字在数组出现的次数，如果有出现数组次数为一的，爱丽丝第一次拿的就是这个数，然后对于次数大于2的，鲍勃哪一个，爱丽丝跟着拿一个，对于另外出现次数为一的，鲍勃肯定会拿，所以遍历的时候，第一次出现次数为1的，设一个标记变量（爱丽丝第一次拿），再一次出现次数为1的（肯定被鲍勃拿了，就break）
const int N = 2e5 + 10;
int a[N];
int b[N];
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
a[x]++;
}
int ok = 0;
for (int i = 0; i <= n+1; i++)
{
if (a[i] == 0)
{
cout << i << '\n';
break;
}
else if(a[i]==1)
{
if(ok==0)
ok = 1;
else
{
cout << i << '\n';
break;
}
}
}
memset(a, 0, sizeof(a));
}
