MEX Reordering - Codeforces Solution • MuXinCG's Blog

判断能否重排数组，使得对所有分割点，前缀的 MEX 与后缀的 MEX 不相等。本文分析了零和一的数量对答案的决定性影响。

题目描述#

给定一个长度为 $n$ 的整数数组 $a$ 。

定义 $f(l, r) = \operatorname{MEX}([a_l, a_{l+1}, \ldots, a_r])$ ，其中 $\operatorname{MEX}$ 表示一个集合中未出现的最小非负整数。

判断是否存在一种重排方式，使得对每个 $i$ （ $1 \le i \le n - 1$ ），都有

f(1, i) \neq f(i + 1, n)

即对于任意分割点 $i$ ，前缀 $[1, i]$ 的 MEX 与后缀 $[i+1, n]$ 的 MEX 不同。

若存在输出 YES，否则输出 NO。

思路分析#

首先我们看到 MEX，众所周知，MEX 是一个非常严格的约束。我们可以从 0 开始讨论，容易看出，若将所有的零集中到序列开始，那么在 0 序列结束后所有的分割都能使得 MEX 不相同。这是因为分割右边没有 0，则 MEX 必为 0，分割右边有 0，则 MEX 必不为零。这样，我们就可以对 0 的个数进行讨论，我们大致分了三种情况，包含所有的可能情景

0 的个数为 0 时
0 的个数为 1 时
0 的个数大于等于 2 时

当 0 的个数为 0 时#

0 的个数为 0 时，此时对于任意排列，显而易见的是其任意一个分割左右序列均没有 0，则 MEX 均为 0，所以我们输出 NO。

当 0 的个数为 1 时#

我们将 0 放在首位，对于任意分割，左序列有 0，右序列没有 0，则左序列 MEX $\neq 0$ ，右序列 MEX $= 0$ ，所以我们输出 YES。

当 0 的个数大于等于 2 时#

我们再次分类讨论，当我们没有 1 时，对于任意排列，选择任意一对 0 的中间位置，此时无论如何，左右 MEX 均为 1（因为左右均有 0 且均无 1），因此，假如没有 1，对于任意一个排列，我们总能找到一个切割使得左右序列 MEX 值相同，我们输出 NO。

当我们有 1 时，我们可以构造一个序列， $0\cdots 0\ 1\cdots 1 \cdots$ ，即将 0 放在首位，1 放在 0 后，对于切割在 0 序列中的情况，我们有左 MEX $= 1$ ，右 MEX $\ge 1$ ；对于切割在 01 之间或者在 1 中间的情况，我们有左 MEX $= 1$ ，右边 MEX $= 0$ ；对于切割在 1 后的情况，我们有左 MEX $\ge 2$ ，右 MEX $= 0$ 。综上所述这是一个合法序列，我们输出 YES。

代码实现#

// Problem: 1073DIV2
// URL: https://codeforces.com/contest/1073/problem/DIV2
// Tags: B
//    ███╗   ███╗██╗   ██╗██╗  ██╗██╗███╗   ██╗ ██████╗ ██████╗ 
//    ████╗ ████║██║   ██║╚██╗██╔╝██║████╗  ██║██╔════╝██╔════╝ 
//    ██╔████╔██║██║   ██║ ╚███╔╝ ██║██╔██╗ ██║██║     ██║  ███╗
//    ██║╚██╔╝██║██║   ██║ ██╔██╗ ██║██║╚██╗██║██║     ██║   ██║
//    ██║ ╚═╝ ██║╚██████╔╝██╔╝ ██╗██║██║ ╚████║╚██████╗╚██████╔╝
//    ╚═╝     ╚═╝ ╚═════╝ ╚═╝  ╚═╝╚═╝╚═╝  ╚═══╝ ╚═════╝ ╚═════╝ 

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200;

int n;

void solve() {
    cin >> n;
    int temp = 0, cnt[2] = {0, 0};

    for (int i = 1; i <= n; i++) {
        cin >> temp;
        if (temp <= 1) cnt[temp]++;
    }
    if (cnt[0] == 0) {
        cout << "NO\n";
    } else {
        if (cnt[0] == 1) cout << "YES\n";
        else {
            if (cnt[1]) cout << "YES\n";
            else { cout << "NO\n"; }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

cpp

复杂度分析#

由于只进行了一次遍历，所以整体复杂度为 $O(n)$ 。

MEX Reordering - Codeforces Solution