CF1806B Mex Master 题解

· · 题解

首先本题的思路是贪心

根据题意，数组$[a_i]$在改变任意次后需要求解 $MEX\dagger[a_1+a_2,a_2+a_3,…,a_{n-1}+a_n]$的最小值。 ### 因此由小到大考虑 1. 答案为 $0$ 的情况：经过构造后的数组两两相加一定可以大于0 ,构造 $ \{ 0\quad a_1\quad 0\quad a_2\quad \cdots \quad a_i \quad 0\} 
可以发现 此时 $0$ 数量  $=i+1(a_i\ne0 , 2i+1=n)$，并且此时 $0$ 的数量为最大值

  1. 答案不为 0 的情况： 若 0 的数量>i+1

    \{0\quad a_1\quad 0\quad a_2\quad \cdots \quad a_i \quad 0\quad\cdots\quad 0\}

    为方便观察，重新排列使其成为不严格递增的数组 (a_i>a_{i-1}>0)

    \{0\quad 0\quad 0\quad\cdots\quad 0\quad a_1\quad a_2\quad \cdots \quad a_i \}

    显然，0+a_1可以决定答案，对于 a的最大值a_i，如果a_i>1,则可以交换(a_1,a_i)答案即为 1。

    剩余情况如下答案为 2

    \{0\quad 0\quad 0\quad\cdots\quad 0\quad 1\quad 1\quad \cdots \quad 1 \}

  2. 特殊情况，若数组内 a 全为 0 (\forall a_i=0)，答案为1。

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    int t, n;
    cin >> t;
    while (t--)
    {
        int find_0 = 0, find_1 = 0, a;
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            cin >> a;
            if (!a)
                find_0++;
            else if (a == 1)
                find_1++;
        }
        if (find_0 <= n - find_0 + 1)
            cout << 0 << endl;
        else if (find_1 + find_0 != n || find_0 == n) // a里有比1大的数或者全是0
            cout << 1 << endl;
        else
            cout << 2 << endl;
    }
    return 0;
}