题解 CF2207E1 【N-MEX (Constructive Version)】

Leasier · 2026-03-09 17:49:04 · 题解

方便起见，令 a_0 = n, b_0 = 10^9。

考虑 a_i 所能提供的信息：b_0, b_1, \cdots, b_i 中 < a_i 的项的数量为 \text{need}_i = (a_i + 1) - (n - i + 1)。这引出了有解的第一个条件：

• (1) 0 \leq \text{need}_i \leq i, \forall 1 \leq i \leq n。

另外，注意到在从 a_i 到 a_{i + 1} 的过程中，若 b_{i + 1} < a_i 且 b_{i + 1} 没有被用过则 a_i = a_{i + 1}，若 b_{i + 1} \geq a_i 或 b_{i + 1} 被用过则 a_i > a_{i + 1}。这引出了有解的第二个条件：

• (2) a_i \geq a_{i + 1}, \forall 1 \leq i < n。

当 (1)(2) 皆满足，考虑一步一步构造：

• 第一类填数：若 a_i = a_{i - 1}，贪心地，令 b_i 为 \{0, \cdots, n\} \backslash a 中 < a_i 且没有被用过的最大数。
• 第二类填数：若 a_i < a_{i - 1}，我们需要填入一个 \geq a_{i - 1} 或被用过的数。
• 考虑取 b_i = 10^9。由于 a 单调不增，这个数必然不会对 a_{i + 1 \sim n} 的值产生任何影响。

那么，只要满足 (1)(2)，这一算法就一定能构造出一组解吗？事实上是可以的：

• 设 a_{0 \sim n} 可以被划分为 k 个 a 值相同的连续段，其中第 i 段的长度为 l_i。
• 则我们一共进行了 \displaystyle\sum_{i = 1}^k (l_i - 1) = (n + 1) - k 次第一类填数。
• 注意到 \{0, \cdots, n\} \backslash a 中也恰好有 (n + 1) - k 个数，因此只需说明：讨论 a_i 时，取出 \{0, \cdots, n\} \backslash a 中没有被用过的最大数，其一定 < a_i。
• 而当我们进入第 i 段，首项下标为 p = \displaystyle\sum_{j = 1}^{i - 1} l_j，前面有 i - 1 个 a 值和 \displaystyle\sum_{j = 1}^{i - 1} (l_j - 1) 个第一类填数指定的 b 值，合计恰 p 个数；再加上 a_p 自身，可知下一次第一类填数指定的 b 值不应超过 n - p - 1，而 (1) 指出 n - p \leq a_p，故 n - p - 1 < a_p，遂合法。

综上，时间复杂度为 O(\sum n)。

代码：

#include <stdio.h>

int a[200001], b[200001];
bool mark[2000001];

void solve(){
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i++){
        int need = (a[i] + 1) - (n - i + 1);
        if (need < 0 || need > i){
            printf("NO\n");
            return;
        }
    }
    a[0] = n;
    for (int i = 1; i <= n; i++){
        if (a[i] > a[i - 1]){
            printf("NO\n");
            return;
        }
    }
    for (int i = 0; i <= n; i++){
        mark[i] = true;
    }
    for (int i = 0; i <= n; i++){
        mark[a[i]] = false;
    }
    for (int i = 1, j = n; i <= n; i++){
        if (a[i] == a[i - 1]){
            while (j >= 0 && !mark[j]) j--;
            b[i] = j--;
        } else {
            b[i] = 1e9;
        }
    }
    printf("YES\n");
    for (int i = 1; i <= n; i++){
        printf("%d ", b[i]);
    }
    printf("\n");
}

int main(){
    int t;
    scanf("%d", &t);
    for (int cas = 1; cas <= t; cas++){
        solve();
    }
    return 0;
}