《蓝桥杯省赛压轴》隐形前缀和应用（难度：***）
题目：灵能传输 方法：前缀和 链接：灵能传输 - 蓝桥云课 (lanqiao.cn)
题目大意：首先会给定一个数组a，每一次操作是将其中连续的三个数做加减，经过一系列操作得到一个新的数组，问其中所有绝对值最大的数最小可以多大，有点绕，，，
思路：通过题目可以看到，不管是两边向中间传输，还是中间向两边传输，都可以满足，这三个数的总和是不变的，所以通过验证对三个连续的数进行一系列操作后前缀和的变化可以得到s[i]与s[i-1]二者互相交换，然而s[i+1]的值始终不变，根据这个规律可以将其扩展至整个数列，也就是s数组中除s[0]和s[n]以外，其他s[i]可以去任意的位置，而问题所求的ai，就可以用s数组中连续的两项做差得到，而这道题已经被我们转化为就是构造一个每一项尽可能小的数组，其中的每一个元素为s数组中连续两项之差，然后求这个构造数组所有元素中最大的元素，而这里由于上文分析s[0]与s[n]始终是不变的，所以这里有涉及了两种情况：
（1）：如果s[0]刚好是s数组的最小值，s[n]刚好是s数组的最大值，只需排序后就可输出max{s[i]-s[i-1]}；
（2）：一般情况s[0]与s[n]在排列后s数组的任何位置，所以贪心的按照路线s[0]->min->max->s[n]这样的路线获得，为了避免路线1和路线3出现重叠所以构造s1与s3数列时，隔位选取做到全局最优，并且路线2不能走已经用过的元素，所以又使用vis进行优化记录，最后获取连续两项差的最大值。
注意：此方法为构造数组的解法，中间需要运用贪心获取最优路线的思想，正确性暂时满足，极限数据不一定能保证此代码的正确性（我还无法证明可以满足所有极限数据
）
）#include<bits/stdc++.h>n
using namespace std;
const int N=3e5;
long long a[N],s[N];
bool vis[N];
int main(){
int T; scanf("%d",&T);
while(T--){
memset(vis,0,sizeof(vis));
int n; scanf("%d",&n);
s[0]=0;
for(int i=1;i<=n;++i){
scanf("%lld",&s[i]);
s[i] += s[i-1]; //计算前缀和
}
long long 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)
//图中的路线1: 从s0到min。隔一个数取一个
a[l++]=s[i], vis[i]=1;
for(int i = lower_bound(s,s+n+1,sn)-s;i<=n;i+=2)
//图中的路线3: 从max到sn。隔一个数取一个
a[r--]=s[i], vis[i]=1;
for(int i=0;i<=n;++i) //图中的路线2：从min到max
if(!vis[i])
a[l++]=s[i];
long long res=0;
for(int i=1;i<=n;++i)
res = max(res,abs(a[i]-a[i-1]));
printf("%lld\n",res);
}
return 0;
}
投递奇安信等公司7个岗位 >
拼多多一面87人在聊
查看5道真题和解析