CF1798D Shocking Arrangement

给定一个整数数组 $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$ 的绝对值。更正式地说，判断是否存在一个排列 $p_1, p_2, \ldots, p_n$，使得对于数组 $a_{p_1}, a_{p_2}, \ldots, a_{p_n}$，上述条件成立，并输出这样一个数组。回忆一下，数组 $p_1, p_2, \ldots, p_n$ 被称为排列，是指对于每个 $1$ 到 $n$ 的整数 $x$，恰好有一个 $i$ 满足 $p_i = x$。

每组测试数据包含多组测试用例。第一行为测试用例组数 $t$（$1 \le t \le 50000$）。接下来每组测试用例描述如下： 每组测试用例的第一行为一个整数 $n$（$1 \le n \le 300000$），表示数组 $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$ 的总和不超过 $300000$。

对于每组测试用例，如果无法将数组 $a$ 重新排列使其满足要求，输出一行 "No"。 如果可以，第一行输出 "Yes"，第二行输出 $n$ 个数，表示满足条件的排列后的数组 $a_1, a_2, \ldots, a_n$（即 $a_{p_1}, a_{p_2}, \ldots, a_{p_n}$）。 如果有多种答案，可以输出任意一种。

在第一个测试用例中，$\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]$。 由 ChatGPT 4.1 翻译