← 返回题目列表

Codeforces · 1798/D

D. 令人震惊的安排

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

给定一个数组 $$$a_1, a_2, \ldots, a_n$$$,由整数组成,使得 $$$a_1 + a_2 + \ldots + a_n = 0$$$。

您必须重新排列数组 $$$a$$$ 的元素,以满足以下条件:

$$$$$$\max\limits_{1 \le l \le r \le n} \lvert a_l + a_{l+1} + \ldots + a_r \rvert < \max(a_1, a_2, \ldots, a_n) - \min(a_1, a_2, \ldots, a_n),$$$$$$ 其中$$$|x|$$$ 表示$$$x$$$ 的绝对值。

更正式地说,判断对于数组$$$a_{p_1}, a_{p_2}, \ldots, a_{p_n}$$$是否存在满足上述条件的排列$$$p_1, p_2, \ldots, p_n$$$,并找到对应的数组。

回想一下,如果对于从 $$$1$$$ 到 $$$n$$$ 的每个整数 $$$x$$$,从 $$$1$$$ 到 $$$n$$$ 正好有一个 $$$i$$$ 使得 $$$p_i = x$$$,则数组 $$$p_1, p_2, \ldots, p_n$$$ 被称为排列。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 300\,000$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。保证数组 $$$a$$$ 的和为零,换句话说:$$$a_1 + a_2 + \ldots + a_n = 0$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$300\,000$$$。

输出

对于每个测试用例,如果无法按要求的方式重新排列数组 $$$a$$$ 的元素,则在一行中打印“No”。

如果可能,在第一行中打印“Yes”,然后在单独的行中打印 $$$n$$$ 数字 — 元素 $$$a_1, a_2, \ldots, a_n$$$ 按有效顺序重新排列 ($$$a_{p_1}, a_{p_2}, \ldots, a_{p_n}$$$)。

如果有多个可能的答案,则可以输出其中任何一个。

示例

输入 #1

7
4
3 4 -2 -5
5
2 2 2 -3 -3
8
-3 -3 1 1 1 1 1 1
3
0 1 -1
7
-3 4 3 4 -4 -4 0
1
0
7
-18 13 -18 -17 12 15 13

输出 #1

Yes
-5 -2 3 4
Yes
-3 2 -3 2 2
Yes
1 1 1 -3 1 1 1 -3
Yes
-1 0 1
Yes
4 -4 4 -4 0 3 -3
No
Yes
13 12 -18 15 -18 13 -17

注意

在第一个测试用例中 $$$\max(a_1, \ldots, a_n) - \min(a_1, \ldots, a_n) = 9$$$。因此,元素可以重新排列为$$$[-5, -2, 3, 4]$$$。很容易看出,对于这样的排列 $$$\lvert a_l + \ldots + a_r \rvert$$$ 始终不大于 $$$7$$$,因此小于 $$$9$$$。

在第二个测试用例中,您可以将数组的元素重新排列为 $$$[-3, 2, -3, 2, 2]$$$。那么子数组 $$$[-3, 2, -3]$$$ 上将达到和的最大模数,并且等于 $$$\lvert -3 + 2 + -3 \rvert = \lvert -4 \rvert = 4$$$,小于 $$$5$$$。

在第四个测试示例中,数组 $$$a$$$ 的任何重新排列都适合作为答案,包括 $$$[-1, 0, 1]$$$。