题目描述
难度分:1600
输入T(≤5×104)表示T组数据。所有数据的n之和≤3×105。
每组数据输入n(1≤n≤3×105)和长为n的数组a(−109≤a[i]≤109)。保证sum(a)=0。
重排a,使得a的任意子数组和的绝对值的最大值<max(a)−min(a)。
如果无法做到,输出No
。否则输出Yes
和重排后的a。
输入样例
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
输出样例
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
算法
构造
注意到a的任意子数组和的绝对值的最大值=max(pre)−min(pre),其中pre是前缀和数组。
如果a中只有0,那么输出No
。否则一定可以重排,遍历i∈[1,n],s=Σik=1a[k],方案如下:
- 初始化s=0,答案b=空列表。
- 如果s≥0,那么把剩余元素中的最小值加到b的末尾。
- 如果s<0,那么把剩余元素中的最大值加到b的末尾。
这可以保证s的最小值是min(a),s的最大值严格小于max(a),因为我们是在s<0的时候才把最大值加到b的末尾。所以有max(s)−min(s)<max(a)−min(a)。
复杂度分析
时间复杂度
排完序之后双指针快速获得剩余元素的最大值或最小值即可,所以瓶颈在于排序,整个算法的时间复杂度为O(nlog2n)。
空间复杂度
除了输入的数组a,并没有开辟其他的显性空间,因此额外空间复杂度就是排序的空间复杂度。以快排为基准,那就是O(log2n);但是如果是堆排,就能做到O(1)。
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 300010;
int T, n, a[N];
void solve() {
sort(a + 1, a + n + 1);
if(a[1] == 0 && a[n] == 0) {
puts("No");
return;
}
puts("Yes");
int l = 1, r = n;
LL s = 0;
for(int i = 1; i <= n; i++) {
if(s >= 0) {
s += a[l];
printf("%d ", a[l++]);
}else {
s += a[r];
printf("%d ", a[r--]);
}
}
puts("");
}
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
solve();
}
return 0;
}