为帮助大家能在6月18日的比赛中有一个更好的成绩,我会将蓝桥杯官网上的历届决赛题目的四类语言题解都发出来。希望能对大家的成绩有所帮助。
今年的最大目标就是能为【一亿技术人】创造更高的价值。
资源限制
内存限制:256.0MB C/C++时间限制:1.0s Java时间限制:3.0s Python时间限制:5.0s
#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)