蓝桥杯官网 试题 PREV-208 历届真题 灵能传输【第十届】【省赛】【研究生组】【C++】【Java】【Python】三种解法

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll s[300005],a[300005];
bool vis[300005];
int main()
{
	ios::sync_with_stdio(0);
	int t; cin>>t;
	while(t--)
	{
		memset(vis,0,sizeof(vis));
		s[0]=0;
		int n; cin>>n;
		for(int i=1;i<=n;i++)
		{
			int x; cin>>x;
			s[i]=s[i-1]+x;
		}
		ll s0=s[0],sn=s[n];
		if(s0 > sn) swap(s0,sn);
		sort(s,s+n+1);
		memcpy(a,s,sizeof(ll)*(n+1));
		int k,top=0;
		for(k=0;k<=n;k++)
		if(s[k]==s0) break;
		for(int i=k;i>=0;i-=2,top++)
		{
			a[top]=s[i];
			vis[i]=true;
		}
		for(int i=0;i<=k;i++)
		{
			if(!vis[i])
			a[top++]=s[i];
		}
		top=n;
		for(k=n;k>=0;k--)
		if(s[k]==sn) break;
		for(int i=k;i<=n;i+=2,top--)
		{
			a[top]=s[i];
			vis[i]=true;
		}
		for(int i=n;i>=k;i--)
		{
			if(!vis[i])
			a[top--]=s[i];
		}
		ll Max=-1;
		for(int i=1;i<=n;i++)
		Max=max(Max,abs(a[i]-a[i-1]));
		cout<<Max<<endl;
	}
	return 0;
} 

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        int N = (int)(3e5 + 10);
        long[] s = new long[N];   //前缀和
        long[] a = new long[N];   //灵能
        boolean[] v = new boolean[N];   //标记数组，标记s[i]是否已被安排

        int t = Input.nextInt();  //多组询问
        while (t --> 0) {
            int n = Input.nextInt();
            s[0] = 0;
            for (int i = 0; i < n; i++)  //求前缀和
                s[i + 1] = s[i] + Input.nextInt();

            long s0 = s[0], sn = s[n];  //两头的前缀和
            if (s0 > sn) {   //如果需要，交换
                s0 ^= sn;
                sn ^= s0;
                s0 ^= sn;
            }
            Arrays.sort(s, 0, n + 1);  //排序，注意s[0], s[n]也参与了排序
            for (int i = 0; i <= n; i++) if (s[i] == s0) {  //s0记住s[0]的位置
                s0 = i;
                break;
            }
            for (int i = n; i >= 0; i--) if (s[i] == sn) { //sn记住s[n]的位置
                sn = i;
                break;
            }
            //安排S[i],使之单调变化
            int l = 0, r = n;
            for (int i = 0; i <= n; i++) v[i] = false;
            for (int i = (int)s0; i >= 0; i -= 2) {
                a[l++] = s[i];
                v[i] = true;
            }
            for (int i = (int)sn; i <= n; i += 2) {
                a[r--] = s[i];
                v[i] = true;
            }
            for (int i = 0; i <= n; i++)
                if (!v[i]) a[l++] = s[i];
            //找出最大灵能
            long ans = 0;
            for (int i = 1; i <= n; i++)
                ans = Math.max(ans, Math.abs(a[i] - a[i - 1]));
            Input.out.println(ans);
            Input.out.flush();
        }
    }

    static class Input {
        static StreamTokenizer streamTokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        static PrintWriter out = new PrintWriter((new OutputStreamWriter(System.out)));
        static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        static int nextInt() throws IOException {
            streamTokenizer.nextToken();
            return (int) streamTokenizer.nval;
        }

        static long nextLong() throws IOException {
            streamTokenizer.nextToken();
            return (long) streamTokenizer.nval;
        }

        static double nextDouble() throws IOException {
            streamTokenizer.nextToken();
            return streamTokenizer.nval;
        }

        static String nextLine() throws IOException {
            return bufferedReader.readLine();
        }

        static char next() throws IOException {
            return (char) bufferedReader.read();
        }
    }
}

ts = int(input())
for t in range(ts):
    n = int(input())
    energy = list(map(int, input().split()))
    s = [0]
    for i,e in enumerate(energy):
        if i == 0:
            s.append(e)
        else:
            s.append(s[i] + e)
    vis = [False] * len(s)
    a = [0] * len(s)
    s0 = s[0]
    sn = s[-1]
    if s0 > sn:
        s0, sn = sn, s0
    s.sort()
    for i in range(len(s)):
        if s[i] == s0:
            s0 = i
            break
    for i in range(len(s)-1,-1,-1):
        if s[i] == sn:
            sn = i
            break
    l, r = 0, n
    for i in range(s0,-1,-2):
        a[l] = s[i]
        l += 1
        vis[i] = True
    for i in range(sn,n+1,2):
        a[r] = s[i]
        r -= 1
        vis[i] = True
    for i in range(n+1):
        if not vis[i]:
            a[l] = s[i]
            l += 1
    ans = 0
    for i in range(1,n+1):
        ans = max(ans,abs(a[i]-a[i-1]))
    print(ans)