A16788. Array Coloring
编程题
普及-
知识点
题目描述
有 $n$ 张卡片排成一行，第 $i$ 张卡片上写有整数 $a_i$，所有整数互不相同。
你需要将每张卡片染成**红色**或**蓝色**，且满足以下两个条件：
1. 原排列中，任意两个相邻的卡片颜色不同；
2. 将所有卡片按数字升序重新排列后，新排列中任意两个相邻的卡片颜色也不同。
请判断是否存在满足要求的染色方式。
你需要将每张卡片染成**红色**或**蓝色**，且满足以下两个条件：
1. 原排列中，任意两个相邻的卡片颜色不同；
2. 将所有卡片按数字升序重新排列后，新排列中任意两个相邻的卡片颜色也不同。
请判断是否存在满足要求的染色方式。
输入格式
输入包含多组测试用例。第一行输入测试用例数 $t$（$1 \le t \le 200$）。
每组测试用例的第一行输入一个整数 $n$（$2 \le n \le 100$），表示数组的长度。
第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）。
保证数组中所有元素互不相同。
每组测试用例的第一行输入一个整数 $n$（$2 \le n \le 100$），表示数组的长度。
第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）。
保证数组中所有元素互不相同。
输出格式
对于每组测试用例，若存在合法的染色方式，输出
输出的大小写不做要求（例如
YES，否则输出 NO。输出的大小写不做要求（例如
yEs、yes、Yes、YES 均视为正确答案）。输入输出样例
输入 #1
4 4 2 3 4 1 3 2 3 1 5 3 4 1 2 5 5 3 1 4 2 5
输出 #1
YES NO YES NO
说明/提示
第一个样例中，卡片的染色方式为 $a = [\color{red}{2}, \color{blue}{3}, \color{red}{4}, \color{blue}{1}]$。升序排序后卡片变为 $[\color{blue}{1}, \color{red}{2}, \color{blue}{3}, \color{red}{4}]$。两种排列均满足相邻颜色不同的条件，因此答案为
第二个样例中，不存在合法的染色方式。例如，若将卡片染为 $a = [\color{blue}{2}, \color{red}{3}, \color{blue}{1}]$，排序后的序列为 $[\color{blue}{1}, \color{blue}{2}, \color{red}{3}]$，其中相邻的 $1$ 和 $2$ 颜色相同，不满足条件。
第三个样例中，一种合法的染色方式为 $a = [\color{blue}{3}, \color{red}{4}, \color{blue}{1}, \color{red}{2}, \color{blue}{5}]$。升序排序后卡片变为 $[\color{blue}{1}, \color{red}{2}, \color{blue}{3}, \color{red}{4}, \color{blue}{5}]$，满足所有条件。
YES。第二个样例中，不存在合法的染色方式。例如，若将卡片染为 $a = [\color{blue}{2}, \color{red}{3}, \color{blue}{1}]$，排序后的序列为 $[\color{blue}{1}, \color{blue}{2}, \color{red}{3}]$，其中相邻的 $1$ 和 $2$ 颜色相同，不满足条件。
第三个样例中，一种合法的染色方式为 $a = [\color{blue}{3}, \color{red}{4}, \color{blue}{1}, \color{red}{2}, \color{blue}{5}]$。升序排序后卡片变为 $[\color{blue}{1}, \color{red}{2}, \color{blue}{3}, \color{red}{4}, \color{blue}{5}]$，满足所有条件。