题目描述
在游戏《星际争霸 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,|a_i|<=10^9$
每个评测的限制如下
贪心
1.性质分析:
(1).$a_{i+1}+=a_i,a_{i-1}+=a_i,a_i-=2a_i$
(2).考虑前缀和:对于每次操作,相当于交换了s[i-1]和s[i],对于s[i+1]无影响,要求|a|最小即将前缀和数组按升序排列,找出前缀和中的最大差值即可即可(反证法可证)
(3).令s[0]=0,由于交换对s[i+1]无影响,这样数据的两端就确定下来了且是无法改变的——这个s[0]的固定很关键
(4).由于头尾两点无法改变,我们只有两条路径可以使序列的差值最小:s[0]->最小值->最大值->s[n];s[0]->最大值->最小值->最大值.以下标i为x轴,以s[i]为y轴,比较两条曲线可知第一种策略下最多只有两层的波折——需要隔1个跳(具体表示的意思见(5)),而在第二种策略下最多有三层的波折——需要隔两跳,隔着跳的越多,也就意味着间隔越大,所以第一种策略更优
(5).思考贪心的策略:假设初值较小,终值较大(因为显然我们在乎的并不是实际的序列,而仅仅是序列的最大差值——而这不论是$s_0<=s_n,还是s_n<=s_0$情况下都是唯一的).$s_0$到最小值段隔着跳,最大值到$s_n$段隔着跳,最小值段到最大值段直接收录剩下的元素.(注意:奇数和偶数情况略有不同)
对于隔着跳是最优策略的证明——反证法:
设有$a_0,a_1,a_2,a_3$,且$a_0$为端点,假设$a_2直接到a_1段是最优,那么回来是必然至少是a_0->a_3,显然|a_3-a_0|>=|a_2-a-1|,与假设矛盾,原命题成立 注意:在实际中对排好序的数组进行操作时,我们可以将它们分成三段:最小值->s[0],s->[n]->最大值,其它$
错误样例
输入
3
8
897 193 746 16 937 104 366 -858
8
-191 885 881 -428 380 -216 287 -673
8
-309 -779 651 -969 237 564 610 -168
输出
1041
885
651
标准答案(注:arr[i]为辅助观察的数据,是排好最终次序的s[i])
arr[i] :897 1090 1836 1852 2893 3259 2789 2401
1041
arr[i] :-191 694 1311 1575 1598 1527 1147 925
885
arr[i] :-437 -1088 -1406 -1169 -605 -309 5 0
651
错误分析:
第一组数据错误,可以看到在最大值3259两边的数据应该互换位置,将其一般化看.设$a_0<=a_1<=a_2<=a_3<=a_4$,且$a_1就是我们要找的未排序前的last$(也就是最大值的右端序列).
(1).依照间隔跳的方法4->1,那么获得序列最终为$,a_0,a_3,a_4,a_2,a_1$
(2).依照间隔跳的方法1->4,那么获得序列最终为$a_0,a_2,a_4,a_3,a_1$
对比以上两个可以看到偶数个数下(4-1),虽然最终都会出现隔着0个跳的情况,但是由于经过$a_2$跳到$a_1$会阻塞向下的道路(这样从左边来的路只能为$a_3->a_0$),而第二种情况下$a_4$不需要向上跳了,所以不会造成阻塞.
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
//注意有多组输入
using namespace std;
typedef long long ll;
const int N=3e5+10;
ll s[N],arr1[N],arr2[N],arr[N];
bool st[N];
int main()
{
int t;
cin >> t;
while(t--){
int n;
cin >> n;
ll temp;
memset(s,0,sizeof s);
memset(st,false,sizeof st);
for(int i=1;i<=n;i++){
scanf("%lld",&temp);
s[i]=s[i-1]+temp;
//printf("s[%d]=%I64d\n",i,s[i]);
}
//保证最小值在前,最大值在后
if(s[n]<s[0]){
swap(s[0],s[n]);
}
ll first=s[0],second=s[n];
sort(s,s+n+1);
for(int i=0;i<=n;i++){
if(s[i]==first){
first=i;
break;
}
}
for(int i=n;i>=0;i--){
if(s[i]==second){
second=i;
break;
}
}
//也可以先计算第一段
int cnt1=0,cnt2=0;
for(int i=first;i>=0;){
arr1[++cnt1]=s[i];
st[i]=true;
if(i-2>=0){
i-=2;
}
else{
i-=1;
}
}
//避免first=last,相向而取(当然从图像看也是相对的)
for(int i=second;i<=n;){
arr2[++cnt2]=s[i];
st[i]=true;
if(i+2<=n){
i+=2;
}
else{
i+=1;
}
}
int cnt=-1;
//s[0]到最小值
for(int i=1;i<=cnt1;i++){
arr[++cnt]=arr1[i];
}
for(int i=0;i<=n;i++){
if(!st[i]){
arr[++cnt]=s[i];
}
}
for(int i=cnt2;i>=1;i--){
arr[++cnt]=arr2[i];
}
ll ans=arr[1]-arr[0];
//cout << "arr[i] :";
for(int i=1;i<=n;i++){
//cout << arr[i] << ' ';
ans=max(ans,abs(arr[i]-arr[i-1]));
}
//cout << endl;
cout << ans << endl;
}
return 0;
}
