CF1798D.Shocking Arrangement
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are given an array a1,a2,…,an consisting of integers such that a1+a2+…+an=0 .
You have to rearrange the elements of the array a so that the following condition is satisfied:
1≤l≤r≤nmax∣al+al+1+…+ar∣<max(a1,a2,…,an)−min(a1,a2,…,an)
where ∣x∣ denotes the absolute value of x .More formally, determine if there exists a permutation p1,p2,…,pn that for the array ap1,ap2,…,apn , the condition above is satisfied, and find the corresponding array.Recall that the array p1,p2,…,pn is called a permutation if for each integer x from 1 to n there is exactly one i from 1 to n such that pi=x.
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t ( 1≤t≤50000 ). The description of the test cases follows.
The first line of each test case contains a single integer n ( 1≤n≤300000 ) — the length of the array a .
The second line of each test case contains n integers a1,a2,…,an ( −109≤ai≤109 ) — elements of the array a . It is guaranteed that the sum of the array a is zero, in other words: a1+a2+…+an=0 .
It is guaranteed that the sum of n over all test cases does not exceed 300000 .
输出格式
For each test case, if it is impossible to rearrange the elements of the array a in the required way, print "No" in a single line.
If possible, print "Yes" in the first line, and then in a separate line n numbers — elements a1,a2,…,an rearranged in a valid order ( ap1,ap2,…,apn ).
If there are several possible answers, you can output any of them.
输入输出样例
输入#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
说明/提示
In the first test case max(a1,…,an)−min(a1,…,an)=9 . Therefore, the elements can be rearranged as [−5,−2,3,4] . It is easy to see that for such an arrangement ∣al+…+ar∣ is always not greater than 7 , and therefore less than 9 .
In the second test case you can rearrange the elements of the array as [−3,2,−3,2,2] . Then the maximum modulus of the sum will be reached on the subarray [−3,2,−3] , and will be equal to ∣−3+2+−3∣=∣−4∣=4 , which is less than 5 .
In the fourth test example, any rearrangement of the array a will be suitable as an answer, including [−1,0,1] .