A16836. MEX Reordering
编程题
普及-
知识点
题目描述
给定一个由 $n$ 个元素组成的整数数组 $a$，定义 $f(l, r) = \operatorname{MEX}([a_l, a_{l + 1}, \dots, a_r])$ $^{∗}$。
请判断是否可以对数组 $a$ 进行**重排**，使得对于每一个 $i$（$1 \le i \le n - 1$），都满足 $f(1, i) \neq f(i + 1, n)$。换句话说，对于每一个分割点 $i$，数组**前缀**的MEX值必须与**后缀**的MEX值不同。
$^{∗}$ 一个整数集合 $c_1, c_2, \dots, c_k$ 的最小未出现值（MEX）定义为：**不在该集合中出现的最小非负整数**。
请判断是否可以对数组 $a$ 进行**重排**，使得对于每一个 $i$（$1 \le i \le n - 1$），都满足 $f(1, i) \neq f(i + 1, n)$。换句话说，对于每一个分割点 $i$，数组**前缀**的MEX值必须与**后缀**的MEX值不同。
$^{∗}$ 一个整数集合 $c_1, c_2, \dots, c_k$ 的最小未出现值（MEX）定义为：**不在该集合中出现的最小非负整数**。
输入格式
输入包含多组测试用例。第一行输入测试用例数 $t$（$1 \le t \le 500$），后续为各测试用例的描述。
每组测试用例的第一行输入一个整数 $n$（$2 \le n \le 100$），表示数组的长度。
第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le n$）。
每组测试用例的第一行输入一个整数 $n$（$2 \le n \le 100$），表示数组的长度。
第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le n$）。
输出格式
对于每组测试用例，若存在满足条件的重排方式，输出``
输出的大小写不做要求（例如
YES`，否则输出 `NO``。输出的大小写不做要求（例如
yEs、yes、Yes、YES 均视为正确答案）。输入输出样例
输入 #1
3 2 1 0 3 0 3 0 6 1 0 5 0 6 1
输出 #1
YES NO YES
说明/提示
第一个样例中，数组的原始顺序就已经满足条件。此时唯一的分割点为 $i=1$，计算得 $f(1,1) = \operatorname{MEX}([1]) = 0$，$f(2,2) = \operatorname{MEX}([0]) = 1$。由于 $0 \neq 1$，条件成立。
第二个样例中，可以证明不存在满足条件的重排方式。例如考虑重排后的数组为 $[3, 0, 0]$，取分割点 $i=2$，则$f(1,2) = \operatorname{MEX}([3,0]) = 1$，$f(3,3) = \operatorname{MEX}([0]) = 1$，二者相等，因此该重排方式无效。
第三个样例中，可将数组重排为 $[1, 6, 1, 0, 0, 5]$。以分割点 $i=4$ 为例，$f(1,4) = \operatorname{MEX}([1,6,1,0]) = 2$，$f(5,6) = \operatorname{MEX}([0,5]) = 1$，满足条件。可以验证，该重排方式对所有分割点均满足条件。
第二个样例中，可以证明不存在满足条件的重排方式。例如考虑重排后的数组为 $[3, 0, 0]$，取分割点 $i=2$，则$f(1,2) = \operatorname{MEX}([3,0]) = 1$，$f(3,3) = \operatorname{MEX}([0]) = 1$，二者相等，因此该重排方式无效。
第三个样例中，可将数组重排为 $[1, 6, 1, 0, 0, 5]$。以分割点 $i=4$ 为例，$f(1,4) = \operatorname{MEX}([1,6,1,0]) = 2$，$f(5,6) = \operatorname{MEX}([0,5]) = 1$，满足条件。可以验证，该重排方式对所有分割点均满足条件。