【蓝桥杯】2019年第十届蓝桥杯省赛B组试题J — 灵能传输（前缀和，猜想结论）难度⭐⭐⭐⭐

蓝桥杯的题还是有难题的。这道题的可行性证明比较麻烦，但是代码比较简单。
学到了新的序列操作。前缀和的应用，前缀和还是学的不够扎实，晚上再复习一遍。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(int i=s;i<=t;++i)
#define lver(i,t,s) for(int i=t;i>=s;--i)
using namespace std;
typedef long long ll;
const ll N=3e5+7;
const ll INF=1e13+7;
const ll mod=2147483647;
const double EPS=1e-6;
ll n,m,t;
bool vis[N];
ll a[N],s[N],b[N];
int main()
{
    scanf("%lld",&t);
    while(t--)
    {
        memset(vis,0,sizeof vis);
        s[0]=0;
        scanf("%lld",&n);
        over(i,1,n)scanf("%lld",&b[i]);
        over(i,1,n)s[i]=s[i-1]+b[i];
        ll st=s[0],se=s[n];//s[n]是不能变的
        if(st>se)swap(st,se);
        sort(s,s+1+n);
        over(i,0,n)
        {
            if(s[i]==st)
            {
                st=i;
                break;
            }
        }
        lver(i,n,0)
        {
            if(s[i]==se)
            {
                se=i;
                break;
            }
        }
        ll l=0,r=n;
        for(int i=st;i>=0;i-=2)
            a[l++]=s[i],vis[i]=true;
        for(int i=se;i<=n;i+=2)
            a[r--]=s[i],vis[i]=true;
        over(i,0,n)
        if(!vis[i])
            a[l++]=s[i];
        ll res=0;
        over(i,1,n)
        res=max(res,abs(a[i]-a[i-1]));
        printf("%lld\n",res);
    }
    return 0;
}

详解链接