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