题目描述

在游戏《星际争霸 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,
每个评测用例的限制如下：

QQ截图20191205220735.png

输入样例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

样例解释
样例一
对于第一组询问：
对 2 号高阶圣堂武士进行传输操作后 a1=3，a2=2，a3=1。答案为 3。
对于第二组询问：
这一组高阶圣堂武士拥有的灵能都正好可以让他们达到最佳战斗状态。

难度：中等
时/空限制：1s / 64MB
总通过数：407
总尝试数：1025
来源：第十届蓝桥杯省赛C++B/研究生组,第十届蓝桥杯省赛JAVAB组
算法标签

算法1

搞了好久这题，终于明白了，过程分的有点多，而且每一个过程都不是很容易想到，所以会觉得听完y总讲的后感觉根本没听懂，我是也是前后听了好几遍才明白的，然后把思路大致整理一下

搞明白这一题就一定要时刻铭记我们的最终目标是什么。
根据题意我们的最终目标就是使得每个战士的灵能的不稳定度最小，就是经过变化后，序列里的所有数离0最大值最小
可以考虑我们所要求的序列是 $ a_i $ 那么可以考虑用前缀和数组来表示 $ a_i $ 就是 $s_i - s_{i-1}$
那么有了这个基础我们来看题目要求的数据变化，形式化来讲就是 $ a_{i−1} += a_i , a_{i+1} += a_i, a_i −= 2·a_i$
考虑 $ a $ 序列的变化对于 $ s $ 数组的影响，可以看出加了2个 $ a_i $ 同时减了2个 $ a_i $那么对于$s_{i + 1}$ 以及后面$s_{i+k}$来说都没有任何影响，看$s_{i - 1}$ 可以看出多加了一个$a_i$ 所以$s_{i-1}$变为$s_i$ 看$s_i$
可以看出$a_{i-1}$ 加了一个 $a_i$ ,$a_i$减了两个$a_i$所以 $s_i$ 总共减了一个 $a_i$变为$s_{i-1}$
过程①总结一下:

• 考虑用前缀和来表示 $ a_i $ ，找出了经题目要求变化$s_{前}$与$s_{后}$的区别 这也是最难想到的一步

• 这意味着除了s[0]和s[n]以外$ 1 - n $ 的任何s[i]可以进行相互交互从而得到一个有序的序列，而a[i]=s[i]-s[i-1]，也就意味着可以通过交换s[i]的方式得到灵能传输后最终结果

• 根据题意我们要求的是 $a_i$ 距 0 的最大值最小是多少， 转化为 $s_i - s_{i - 1}$ 最大值最小是多少

这样就引出了我们的我第二步,什么样的前缀和序列使得max(s[i] - s[i-1])最小，利用贪心的思路知：有序的前缀和序列使得所求最小

下面是这一思路的证明：一个序列一定存在一个最大值和一个最小值，如果不是有序序列的话，即最大值和最小值不在两边的时候，就会出现曲线，如图：

这样就会存在最大值和最小值刚好相邻，但是求其差值回为最大。其实分析到这里这个题的大体就结束了，但是狗就狗在
s0 和 sn 不能计算到排序中，因为a0 和 an 在两边导致s0 和 sn的 位置固定，我们无法修改这两个数的位置，那么就使得我们最终得到的si序列不是单调的

这就引出了我们的第③步
在一直s0和sn的前提下，怎样使得我们得到的序列满足我们的要求呢，要求是什么，这一点很重要，千万别忘，否则就很难理解这一步，回头翻翻开头和第一步。

第三步：

在s0和sn无法改变在序列中位置的前提下，怎样满足我们要求呢：
下面给出两种一般情况

这里假设s0 是小于sn的（如果是大于，swap一下就是一样的）那么明显第一个图的在y轴视角的叠次数更多，而第二个图的重叠次数更少，重叠次数更小说明我们所求的s[i] - s[i-1]会更大，这样才能保证是求得最大值，如果重叠次数越多那就说明压到y轴时越稠密，那么就是最大值了

分析到这里就完成了第三步，还剩下最后一步，经过我的理解，我发现了 很透彻 最后一步的讲解，为什么要跳着取而不是顺序取

完事完事，真滴难

c++代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 300010;
typedef long long LL;

int n;
LL a[N], s[N];
bool st[N];

int main()
{
    int t;
    scanf("%d", &t);
    while(t -- )
    {
        scanf("%d", &n);
        s[0] = 0;
        for(int i = 1; i <= n; i ++ ) 
        {
            scanf("%lld", &a[i]);
            s[i] = s[i - 1] + a[i];
        }

        LL s0 = s[0], sn = s[n];
        if(s0 > sn) swap(s0, sn);

        sort(s, s + n + 1);

        for(int i = 0; i <= n; i ++ )
            if(s[i] == s0) 
            {
                s0 = i;
                break;
            }

        for(int i = n; i >= 0; i -- )
            if(s[i] == sn)
            {
                sn = i;
                break;
            }

        memset(st, 0,sizeof st);
        int l = 0 ,r = n;

        for(int i = s0; i >= 0; i -= 2)
        {
            a[l ++ ] = s[i];
            st[i] = true;
        }

        for(int i = sn; i <= n; i += 2)
        {
            a[r -- ] = s[i];
            st[i] = true;
        }

        for(int i = 0; i <= n; i ++ )
            if(!st[i]) a[l ++ ] = s[i];


        LL res = 0;

        for(int i = 1; i <= n; i ++ ) res = max(res, abs(a[i] - a[i - 1]));

        printf("%lld\n", res);
    }

    return 0;
}