← 返回题目列表

Codeforces · 2124/I

I. 字典分区

中文机器翻译题面 查看原题

给定一个数组 $$$a$$$,定义 $$$f(a)$$$ 如下:

  • 令 $$$k$$$ 为整数,$$$1 \leq k \leq n$$$。
  • 将 $$$a$$$ 划分为 $$$k$$$ 子数组$$$^{\text{*}}$$$ $$$s_1,s_2,\ldots,s_k$$$,使得 $$$s_1+s_2+\ldots+s_k=a$$$。这里,$$$+$$$表示数组串联。
  • 设 $$$b$$$ 为空数组。对于从 $$$1$$$ 到 $$$k$$$ 的每个 $$$i$$$,将 $$$s_i$$$ 的最小元素附加到 $$$b$$$ 的末尾。
  • 在所有可能的 $$$k$$$ 和分区中,$$$f(a)$$$ 是 $$$k$$$ 的值,这样存在一个按字典顺序生成的分区 最大 $$$b$$$$$$^{\text{†}}$$$。

给你 $$$n$$$ 整数 $$$x_1,x_2,\ldots,x_n$$$。请确定是否存在排列$$$^{\text{‡}}$$$ $$$a$$$,使得$$$f([a_1,a_2,\ldots,a_i])=x_i$$$对于每个$$$1 \leq i \leq n$$$。如果存在排列,则打印一个。如果有多个可能的答案,您可以输出任何一个。

$$$^{\text{*}}$$$数组 $$$c$$$ 是数组 $$$d$$$ 的子数组,如果 $$$c$$$ 可以通过从 $$$d$$$ 删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素来获得。

$$$^{\text{†}}$$$当且仅当满足以下条件之一时,数组 $$$c$$$ 按字典顺序小于数组 $$$d$$$:

  • $$$c$$$ 是 $$$d$$$ 的前缀,但是 $$$c \ne d$$$;或
  • 在 $$$c$$$ 和 $$$d$$$ 不同的第一个位置,数组 $$$c$$$ 的元素比 $$$d$$$ 中的相应元素小。

$$$^{\text{‡}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2\cdot 10^5$$$) — 表示数组 $$$x$$$ 的长度。

以下行包含 $$$n$$$ 整数 $$$x_1,x_2,\ldots,x_n$$$ ($$$1 \leq x_i \leq i$$$) — 表示数组 $$$x$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,打印 是 如果存在排列,并且 NO 否则。每个字母可以以大写或小写形式输出。您可以以任何大小写(上或下)输出。例如,字符串 “是”, “是”, “是”,和 “是” 将被视为积极响应。

如果答案是肯定的,则在下一行输出 $$$n$$$ 数字的排列。

示例

输入
复制

8
3
1 2 2
2
1 1
3
1 2 1
3
1 2 3
4
1 2 2 4
4
1 2 3 3
5
1 2 3 2 3
9
1 2 3 4 5 4 5 6 6

输出
复制

YES
1 2 3
NO
NO
YES
3 1 2
NO
YES
3 1 2 4
YES
1 4 3 5 2
YES
5 2 1 8 6 9 3 4 7

注意

在第一个测试用例中,$$$[1,2,3]$$$ 是满足输入数组的有效排列:

  • 对于$$$[1]$$$,只有一种分区方式:将$$$a[1]$$$单独分区,所以$$$f([1])=1$$$。
  • 对于$$$[1,2]$$$,有两种分区方式:$$$[1,2]$$$单独分区或$$$[1]+[2]$$$。从第一个分区构造 $$$b$$$ 会产生 $$$b=[1]$$$,从第二个分区构造 $$$b$$$ 会产生 $$$b=[1,2]$$$。第二个按字典顺序更大,因此 $$$f([1,2])=2$$$。
  • 对于$$$[1,2,3]$$$,可以证明最佳划分是$$$[1,2]+[3]$$$,得到$$$b=[1,3]$$$。

在第二个测试用例中,可以证明不存在大小为 $$$2$$$ 且 $$$x_1=x_2=1$$$ 的排列。

在第四个测试用例中,满足条件的一种排列是$$$[3,1,2]$$$。