[蓝桥杯][2019年第十届真题]灵能传输

个人题解链接，历届试题，正在更新中~
题目描述
在游戏《星际争霸 II》中，高阶圣堂武士作为星灵的重要 AOE 单位，在 游戏的中后期发挥着重要的作用，其技能”灵能风暴“可以消耗大量的灵能对 一片区域内的敌军造成毁灭性的伤害。经常用于对抗人类的生化部队和虫族的 刺蛇飞龙等低血量单位。

你控制着 n 名高阶圣堂武士，方便起见标为 1, 2, · · · , n。每名高阶圣堂武士 需要一定的灵能来战斗，每个人有一个灵能值 ai 表示其拥有的灵能的多少(ai 非负表示这名高阶圣堂武士比在最佳状态下多余了 ai 点灵能，ai 为负则表示这 名高阶圣堂武士还需要 −ai 点灵能才能到达最佳战斗状态)。现在系统赋予了 你的高阶圣堂武士一个能力，传递灵能，每次你可以选择一个$i ∈ [2, n − 1]$i∈[2,n−1]，若 $a_i ≥ 0$ai​≥0 则其两旁的高阶圣堂武士，也就是 $i − 1、i + 1$i−1、i+1 这两名高阶圣堂武士会从 i 这名高阶圣堂武士这里各抽取 $a_i$ai​ 点灵能;若 $a_i$ai​ < 0 则其两旁的高阶圣堂武士， 也就是$i − 1, i + 1$i−1,i+1 这两名高阶圣堂武士会给 i 这名高阶圣堂武士 $-a_i$−ai​ 点灵能。形 式化来讲就是 $a_{i−1} += a_i, a_{i+1}+ = a_i, a_i −= 2*a_i$ai−1​+=ai​,ai+1​+=ai​,ai​−=2∗ai​。

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

输入
本题包含多组询问。输入的第一行包含一个正整数 T 表示询问组数。 接下来依次输入每一组询问。
每组询问的第一行包含一个正整数 n，表示高阶圣堂武士的数量。 接下来一行包含n个数$a_1,a_2,··· ,a_n$a1​,a2​,⋅⋅⋅,an​。

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

样例输入
3
3
5 -2 3
4
0 0 0 0
3
1 2 3
样例输出
3
0
3
思路
我们先转化一下题意，首先得发现一点东西。我们设有三个数$a_1,a_2,a_3$a1​,a2​,a3​,其前缀和为$s_1, s_2,s_3$s1​,s2​,s3​,我们对$a_2$a2​使用一次灵能传输后变为$a_1+a_2,-a_2,a_3+a_2$a1​+a2​,−a2​,a3​+a2​，前缀和变为$s_2,s_1,s_3$s2​,s1​,s3​。

题意转化为：每次可以交换相邻的两个数，第一个和最后一个不能交换，最小化相邻两数的差的绝对值。第一个数其实是0,因为第一个武士也要算灵能。
要是所有数字都可以改变的话，那么最优的答案就是排成有序。但是这题是有两个点不能动的，所以我们要分成三部分考虑。 我们记$s_0<s_n$s0​<sn​(第一个数只能和最后一个数交换，交换其实是等价于图变反了，是不会影响结果的)

• 大于$s_0$s0​ 且小于$s_n$sn​的部分，显然这一段我们直接升序就可以做到最小，$我们设这一段的开头为st, 最后一个数为ed$我们设这一段的开头为st,最后一个数为ed
• 接下来两部分分别是$小于s_0$小于s0​ 和$大于s_n$大于sn​，两部分考虑的方式是一样的，所以我们讲$小于s_0$小于s0​部分的怎么排列，首先$s_0$s0​是要放在最前面的，如果我们后面的数都降序排的话，会使得这一段的最后一个数和st的差值会变的很大。如果我们升序排的话右会使得和$s_0$s0​的差变得很大。似乎单调的排始终都会有一个数变得很大。我们再次回到最开始的时侯，我们把$s_0$s0​放在了第一个，那么这一段的最后一个数是st（看第一种情况），st是第一个大于$s_0$s0​的数，我们要找一个数最小化和它的差，那么没错，就是$s_1$s1​了（默认升序排序）。接下来我们要最小化和$s_0$s0​的差，现在和它最近的就是$s_2$s2​，这样我们就可以使得整体的最大值不会很大。

最后其实就变成了下图
最后我们再构造求解就可以。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double Pi = acos(-1);
namespace {
  template <typename T> inline void read(T &x) {
    x = 0; T f = 1;char s = getchar();
    for(; !isdigit(s); s = getchar()) if(s == '-') f = -1;
    for(;  isdigit(s); s = getchar()) x = (x << 3) + (x << 1) + (s ^ 48);
    x *= f;
  }
}
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define _for(n,m,i) for (register int i = (n); i <  (m); ++i)
#define _rep(n,m,i) for (register int i = (n); i <= (m); ++i)
#define _srep(n,m,i)for (register int i = (n); i >= (m); i--)
#define _sfor(n,m,i)for (register int i = (n); i >  (m); i--)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define lowbit(x) x & (-x)
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e6+5;
LL a[N];
LL ans[N];
bool vis[N];
LL Abs(LL x) {
  return x < 0 ? -x : x;
}
int main() {
  int t; scanf("%d", &t);
  while(t--) {
    int n; scanf("%d", &n);
    a[0] = 0;
    _rep(1, n, i) {
      scanf("%lld", a + i);
      a[i] += a[i-1];
    }
    LL a0 = 0, an = a[n], Max = 0;
    int A0, AN;
    sort(a, a + n + 1);
    memset(vis, 0, sizeof vis);
    if(a0 > an) swap(a0, an);
    _rep(0, n, i) if(a0 == a[i]) {A0 = i; break;}
    _rep(0, n, i) if(an == a[i]) {AN = i; break;}
    int l = 0, r = n;
    for(int i = A0; i >= 0; i-=2) ans[l++] = a[i], vis[i] = 1;
    for(int i = AN; i <= n; i+=2) ans[r--] = a[i], vis[i] = 1;
    _rep(0, n, i) if(!vis[i]) ans[l++] = a[i];
    _rep(1, n, i) Max = max(Max, Abs(ans[i] - ans[i-1]));
    printf("%lld\n", Max);  
  }
}