#5712. 「BalticOI 2026」木块

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

题目译自 BalticOI 2026 Day1「Block」

你有 $n$ 个木块，它们有 $k$ 种不同的颜色，排成一行。这些木块的颜色分别为 $c_{1}, c_{2}, \ldots, c_{n}$，且所有颜色编号均在 $1$ 到 $k$ 之间。

若某种颜色的木块所在的平均位置恰好为 $(n+1) / 2$，则称该颜色是平衡的。注意，这个数值不一定为整数。

例如，若有 $7$ 个木块按上述方式排列，颜色 $1$ 的平均位置为 $(1+4+6) / 3 = 11 / 3$，颜色 $2$ 的平均位置为 $(2+3+7) / 3 = 4$，颜色 $3$ 的平均位置为 $5$。因为 $(7+1) / 2 = 4$，所以颜色 $2$ 是平衡的，而颜色 $1$ 和颜色 $3$ 则不是。

你能重新排列这些木块，使得所有颜色都是平衡的吗？

输入格式

输入的第一行包含一个整数 $t$，表示测试用例的数量。

接下来描述各个测试用例，每个测试用例由两行组成：

第一行包含两个整数 $n$ 和 $k$，分别表示积木的数量和颜色的种类数。

第二行包含积木的颜色 $c_{1}, c_{2}, \ldots, c_{n}$。每种颜色至少包含一个积木。

输出格式

对于每个测试用例，若存在一种解决方案，则输出 YES，否则输出 NO。若存在解决方案，则在另一行输出一种可能的排列：即按顺序输出每个位置上的积木颜色。

样例

输入

3
7 2
1 1 1 1 2 2 2
2 2
1 2
2 1
1 1

输出

YES
1 2 2 1 1 1 2
NO
YES
1 1

在第一个测试用例的输出中，颜色 $1$ 是平衡的，因为它的平均位置是 $(1+4+5+6) / 4 = 4$，这等于 $(n+1) / 2$。类似地，颜色 $2$ 的平均位置是 $(2+3+7) / 3 = 4$。因此，两种颜色都是平衡的。

在第二个测试用例中，两种可能的排列方式都不能使颜色平衡。

在第三个测试用例的输出中，颜色 $1$ 的积木出现在位置 $1$ 和 $2$。平均值为 $3 / 2$，所以颜色 $1$ 是平衡的。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq t \leq 100$
• $1 \leq k \leq n \leq 2 \cdot 10^{5}$
• $1 \leq c_{1}, c_{2}, \ldots, c_{n} \leq k$
• 所有 $n$ 的总和不超过 $2 \cdot 10^{5}$

详细子任务附加限制及分值如下表所示。