A. Strange Splitting 详细题解

题目重述

给定一个长度为 $n \ge 3$ 的非降序数组 $a_1 \le a_2 \le \dots \le a_n$。需要将每个元素染成红色或蓝色，满足：

• 红色元素的极差（最大值减最小值）不等于蓝色元素的极差；
• 每种颜色至少有一个元素。

若存在这样的染色方案，输出 YES 及一个染色字符串（R 表示红，B 表示蓝）；否则输出 NO。

核心观察

由于数组已经排序，极差只取决于所选颜色的最小值和最大值。如果所有元素都相等（即 $a_1 = a_n$），则无论怎样划分，任何非空子集的极差都是 $0$，因此无法使两个颜色的极差不相等。所以当 $a_1 = a_n$ 时，答案为 NO。

否则，至少有两个不同的值。此时总存在一种简单的染色方案。

构造方案

方案一：第一个元素染红，其余染蓝

• 红色集合：$\{a_1\}$，极差 $= a_1 - a_1 = 0$。
• 蓝色集合：$\{a_2, a_3, \dots, a_n\}$，极差 $= a_n - a_2$。

如果 $a_n - a_2 \neq 0$，则两个极差不同（$0$ 与一个正数），满足条件。此时输出字符串：第一个字符 R，其余 B。

方案二：最后一个元素染蓝，其余染红

当 $a_n - a_2 = 0$ 时，方案一失败（蓝色极差也为 $0$）。
此时 $a_n = a_2$，意味着从 $a_2$ 到 $a_n$ 全部相等，而 $a_1 < a_n$（因为数组并非全等）。那么：

• 红色集合：$\{a_1, a_2, \dots, a_{n-1}\}$，极差 $= a_{n-1} - a_1$。 由于 $a_{n-1} = a_n$ 且 $a_1 < a_n$，所以极差 $>0$。
• 蓝色集合：$\{a_n\}$，极差 $= 0$。

因此两个极差不同（正数与 $0$）。此时输出字符串：前 $n-1$ 个字符 R，最后一个 B。

为什么两种方案必有一可行？

• 如果 $a_n - a_2 \neq 0$，方案一直接成功。
• 如果 $a_n - a_2 = 0$，则 $a_2 = a_n$，从而 $a_1 < a_n$（因为整个数组不全相等），方案二一定成功。

因此，只要数组不是全等，总能构造出解。

算法步骤

1. 读入 $t$。
2. 对于每个测试用例：
   • 读入 $n$ 和数组 $a$。
   • 若 $a[0] == a[n-1]$，输出 "NO"。
   • 否则：
     • 输出 "YES"。
     • 计算 $blue\_range = a[n-1] - a[1]$。
     • 若 $blue\_range \neq 0$：输出字符串 'R' + string(n-1, 'B')。
     • 否则：输出字符串 string(n-1, 'R') + 'B'。

复杂度

每个测试用例 $O(n)$ 时间，$n \le 50$，$t \le 100$，非常快。

正确性证明

• 必要性：全等时任何子集极差均为 $0$，无法满足“不相等”，故必为 NO。
• 充分性：若不全等，按上述构造总能得到一对极差分别为 $0$ 和正数（或正数和 $0$），因此总是 YES。

示例验证

例1: $[1,1,2,2]$

• $a_1=1, a_n=2$，不全等。
• $blue\_range = 2-1=1 \neq 0$，采用方案一，得 R B R R（样例输出 RBRR一致）。

例2: $[1,2,3,4,5]$

• $blue\_range=5-2=3\neq0$，方案一得 R B B B B，但样例输出为 B B R B B（另一种合法解）。题目允许任意合法解，所以方案一也是正确的。实际上样例用的是另一构造：将中间单个元素染红，其余蓝，极差分别为 $0$ 和 $4$。我们的方案一同样有效。

例3: $[3,3,3]$ 全等，输出 NO。

例4: $[1,2,2,2]$

• $blue\_range = 2-2=0$，采用方案二，得 R R R B（即 RRRB），样例输出 RBBR 是另一种解，两者均合法。

因此算法正确。

总结

本题的关键在于发现：当数组不全相等时，通过将最小值单独染一色，其余染另一色，或者将最大值单独染一色，其余染另一色，总能使两个极差不同。实现上只需简单判断并输出对应字符串即可。这是一道非常简单的构造题，思维难度低，适合入门。