蓝桥杯2019年第十届真题-灵能传输-题解（C++代码）

解题思路:直接在a[i]上操作，没有好的解决办法，考虑一下前缀和，发现问题就转换成了：给定一个序列，重新排列元素顺序，要求s0,sn的位置不能变即固定起点终点 ，使得该序列的相邻两数之差的绝对值最小。 可以证明当该序列单调时，有相邻两数的差值的绝对值最小。

注意事项:
具体思路见：灵能传输 思路解析

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3e5+3;
ll a[N],s[N];
bool vis[N];
int n;
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		memset(vis,0,sizeof(vis));
		scanf("%d",&n);
		s[0]=0;
		for(int i=1;i<=n;++i){
			scanf("%lld",&s[i]);
			s[i]+=s[i-1];
		}
		ll s0=0,sn=s[n];
		if(s0>sn) swap(s0,sn);//前小后大，为方便取数，可避免讨论取数时重复取的问题。 
		sort(s,s+n+1);
		int l=0,r=n;
		for(int i=lower_bound(s,s+n+1,s0)-s;i>=0;i-=2){
			a[l++]=s[i],vis[i]=1;
		}
		for(int i=lower_bound(s,s+n+1,sn)-s;i<=n;i+=2){
			a[r--]=s[i],vis[i]=1;
		}
		for(int i=0;i<=n;++i){
			if(!vis[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;
}