题目描述

在游戏《星际争霸 II》中，高阶圣堂武士作为星灵的重要 AOE 单位，在游戏的中后期发挥着重要的作用，其技能”灵能风暴“可以消耗大量的灵能对一片区域内的敌军造成毁灭性的伤害。

经常用于对抗人类的生化部队和虫族的刺蛇飞龙等低血量单位。

你控制着 n 名高阶圣堂武士，方便起见标为 1,2,⋅⋅⋅,n。

每名高阶圣堂武士需要一定的灵能来战斗，每个人有一个灵能值 ai 表示其拥有的灵能的多少（ai 非负表示这名高阶圣堂武士比在最佳状态下多余了 ai 点灵能，ai 为负则表示这名高阶圣堂武士还需要 −ai 点灵能才能到达最佳战斗状态）。

现在系统赋予了你的高阶圣堂武士一个能力，传递灵能，每次你可以选择一个 i∈[2,n−1]，若 ai≥0 则其两旁的高阶圣堂武士，也就是 i−1、i+1 这两名高阶圣堂武士会从 i 这名高阶圣堂武士这里各抽取 ai 点灵能；若 ai<0 则其两旁的高阶圣堂武士，也就是 i−1,i+1 这两名高阶圣堂武士会给 i 这名高阶圣堂武士 −ai 点灵能。

形式化来讲就是 ai−1+=ai,ai+1+=ai,ai−=2ai。

灵能是非常高效的作战工具，同时也非常危险且不稳定，一位高阶圣堂武士拥有的灵能过多或者过少都不好，定义一组高阶圣堂武士的不稳定度为 maxni=1|ai|，请你通过不限次数的传递灵能操作使得你控制的这一组高阶圣堂武士的不稳定度最小。

输入格式
本题包含多组询问。输入的第一行包含一个正整数 T 表示询问组数。

接下来依次输入每一组询问。

每组询问的第一行包含一个正整数 n，表示高阶圣堂武士的数量。

接下来一行包含 n 个数 a1,a2,⋅⋅⋅,an。

输出格式
输出 T 行。

每行一个整数依次表示每组询问的答案。

数据范围
1≤T≤3,3≤n≤300000,|ai|≤109,

样例

输入样例1：
3
3
5 -2 3
4
0 0 0 0
3
1 2 3
输出样例1：
3
0
3
输入样例2：
3
4
-1 -2 -3 7
4
2 3 4 -8
5
-1 -1 6 -1 -1
输出样例2：
5
7
4

贪心

a1,a2,……,an
(a[i-1],a[i],a[i+1])->(a[i-1]+a[i],-a[i],a[i+1]+a[i])
前缀和(s[i-1],s[i],s[i+1])->(s[i],s[i-1],s[i+1])

所以s[1]~s[n-1]可以任意排列，且s[1]尽可能接近0，|s[n]-s[n-1]|尽可能小，s[2]~s[n-1]如果是单调的一定最优，如果有任意位置是逆序，那么两点间的差距一定会更大（可以画个图自行体会）。令s[0]=0，且s[0],s[n]一定是不能变的
那么就是使|s[1]-s[0]|,|s[2]-s[1]|,……,|s[n]-s[n-1]|中的最大值最小

单调分两种，单调减和单调增，当s[0][HTML_REMOVED]s[n]，那么进行交换，则依然可以利用递增求解，因为只是要求距离，那么将整个图形进行左右翻转，结果是不会变的。

在s[0]到达s数组的最小值的过程中，如果一步到达，那么差值一定会很大，但是如果分几步到达，再单调上升，再一步一步下降直到s[n]，那么会更好，那么怎样一步一步的下降呢

所以隔一个向前跳是最优的

在拿数的过程中，需要各种判断，会很麻烦
将s[0]在向前跳、s[n]在向后跳的过程中，拿到的数标记为已拿，最后再将没有用过的数串起来就是中间单调的数

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;

typedef long long LL;
const int N=300005;

int n;
LL s[N],a[N];
int v[N];

int main(){
    int T;cin>>T;
    while(T--){
        cin>>n;
        s[0]=0;//s[0]一定要放在前面，因为在排序后，s[0]可能变化了，会导致后面的样例出错
        for(int i=1;i<=n;i++){
            cin>>s[i];
            s[i]+=s[i-1];
        }
        LL s0=s[0],sn=s[n];//记录s[0]和s[n]的值，在排序后的序列中找到他们的位置
        if(s0>sn)  swap(s0,sn);
        sort(s,s+n+1);
        memset(v,0,sizeof(v));
        for(int i=0;i<=n;i++){
            if(s[i]==s0){
                s0=i;//记录下标
                v[i]=1;
                break;
            }
        }
        for(int i=0;i<=n;i++){
            if(s[i]==sn&&!v[i]){
                sn=i;//记录下标
                break;
            }
        }
        memset(v,0,sizeof(v));//初始所有都没有拿过
        int l=0,r=n;//把s数组整合为应有的顺序
        for(int i=s0;i>=0;i-=2){
            a[l++]=s[i];
            v[i]=1;
        }
        for(int i=sn;i<=n;i+=2){
            a[r--]=s[i];
            v[i]=1;
        }
        for(int i=0;i<=n;i++){
            if(!v[i]){
                a[l++]=s[i];
            }
        }
        LL ans=0;
        for(int i=1;i<=n;i++)  ans=max(ans,abs(a[i]-a[i-1]));
        cout<<ans<<endl;
    }
    return 0;
}