题目描述

难度分:$1600$

输入$T(\leq 5 \times 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 3 \times 10^5$。

每组数据输入$n(1 \leq n \leq 3 \times 10^5)$和长为$n$的数组$a(-10^9 \leq a[i] \leq 10^9)$。保证$sum(a) = 0$。

重排$a$，使得$a$的任意子数组和的绝对值的最大值$\lt 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 \in [1,n]$，$s=\Sigma_{k=1}^{i}a[k]$，方案如下：

1. 初始化$s = 0$，答案$b=$空列表。
2. 如果$s \geq 0$，那么把剩余元素中的最小值加到$b$的末尾。
3. 如果$s \lt 0$，那么把剩余元素中的最大值加到$b$的末尾。

这可以保证$s$的最小值是$min(a)$，$s$的最大值严格小于$max(a)$，因为我们是在$s \lt 0$的时候才把最大值加到$b$的末尾。所以有$max(s)-min(s) \lt max(a)-min(a)$。

复杂度分析

时间复杂度

排完序之后双指针快速获得剩余元素的最大值或最小值即可，所以瓶颈在于排序，整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

除了输入的数组$a$，并没有开辟其他的显性空间，因此额外空间复杂度就是排序的空间复杂度。以快排为基准，那就是$O(log_2n)$；但是如果是堆排，就能做到$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;
}