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:

1. Alice chooses the element $1$ . After this move, $a=[0,0,1]$ and $c=[1]$ .
2. Bob chooses the element $0$ . After this move, $a=[0,1]$ and $c=[1]$ .
3. Alice chooses the element $0$ . After this move, $a=[1]$ and $c=[1,0]$ .
4. 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));
}