Codeforces Round 1085 (Div. 1 + Div. 2)——CF-2207-E1. N-MEX (Constructive Version)

题目大意

题目描述
定义集合 $S$ 的 $k$-mex 为未在 $S$ 中出现的第 $k$ 小的非负整数。例如，集合 $[1, 2, 1]$ 的 $1$-mex 是 $0$，$2$-mex 是 $3$。

给定一个长度为 $n$ 的非负整数数组 $a_1, a_2, \ldots, a_n$。你需要判断是否存在一个非负整数数组 $b_1, b_2, \ldots, b_n$（其中 $0 \le b_i \le 10^9$），使得对于所有 $1 \le i \le n$，前缀 $[b_1, \ldots, b_i]$ 的 $(n-i+1)$-mex 恰好等于 $a_i$。

如果存在这样的数组，请构造并输出任意一个满足条件的数组 $b$；如果不存在，请报告无解。

输入格式
第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。
每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示数组 $a$ 的长度。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^9$）。
保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式
对于每个测试用例，如果存在满足条件的数组 $b$，第一行输出 YES（不区分大小写），第二行输出 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$0 \le b_i \le 10^9$）。
如果不存在，仅输出一行 NO。

样例数据

Input:
6
3
3 3 1
3
2 1 3
1
0
1
2
4
7 5 2 2
6
6 6 6 4 3 3

Output:
YES
2 0 2
NO
YES
67
NO
NO
YES
5 2 1 5 2 0

样例解释
在第一组测试用例中，$a = [3, 3, 1]$。我们可以验证数组 $b = [2, 0, 2]$ 满足条件：

• 当 $i=1$ 时，需要计算前缀 $[b_1] = [2]$ 的 $(3-1+1)$ 即 $3$-mex。未在数组中出现的非负整数依次为 $0, 1, 3, 4, \dots$，其中第 $3$ 小的是 $3$，等于 $a_1$。

• 当 $i=2$ 时，需要计算前缀 $[b_1, b_2] = [2, 0]$ 的 $(3-2+1)$ 即 $2$-mex。未在数组中出现的非负整数依次为 $1, 3, 4, \dots$，其中第 $2$ 小的是 $3$，等于 $a_2$。

• 当 $i=3$ 时，需要计算前缀 $[b_1, b_2, b_3] = [2, 0, 2]$ 的 $(3-3+1)$ 即 $1$-mex。未在数组中出现的非负整数依次为 $1, 3, 4, \dots$，其中第 $1$ 小的是 $1$，等于 $a_3$。

在第二组测试用例中，$a = [2, 1, 3]$。可以证明不存在任何满足条件的数组 $b$，因此输出 NO。

在第三组测试用例中，$a = [0]$。构造 $b = [67]$ 满足条件，因为前缀 $[b_1] = [67]$ 的 $1$-mex 是 $0$，恰好等于 $a_1$。

思路讲解

AC代码

源代码

心路历程（WA，TLE，MLE……）