《蓝桥杯省赛压轴》隐形前缀和应用(难度:***)

题目:灵能传输            方法:前缀和                 链接:灵能传输 - 蓝桥云课 (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;
}

全部评论

相关推荐

就前几天旅游的时候,打开抖音就经常刷到这类视频:以前是高学历学生、老师、主持人,现在做着团播、擦边主播的工作,以及那些经过精心包装的“职业转型”故事——从铺天盖地的VLOG到所谓的“04年夜场工作日记”,这些内容在初中升学、高考放榜等关键时间节点持续发酵。可以说非常直接且精准地在潜移默化地影响着心智尚未成熟的青少年,使其对特殊行业逐渐脱敏。那我就想问了:某些传播公司、平台运营者甚至某些夜场的老板,你们究竟在传递怎样的价值观?点开那些视频,评论区里也是呈现明显的两极分化:一种是​​经济下行论​​:“现在就业市场已经艰难到这种程度了吗?”​​一种是事实反驳派​​:这些创作者往往拥有名校背景,从事着...
牛客刘北:被环境教育的,为了能拿到足够的钱养活自己,不甘心也得甘心,现在的短视频传播的思想的确很扭曲,但是很明显,互联网玩上一年你就能全款提A6,但你全心全意不吃不喝工作一年未必能提A6,但是在高考中考出现这个的确很扭曲,在向大家传播“不上学,玩互联网也可以轻松年入百万”,不是人变了,是社会在变
预测一下26届秋招形势
点赞 评论 收藏
分享
湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
重生我想学测开:嵌入式的问题,我准备入行京东外卖了
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-02 17:28
25届每天都在焦虑找工作的事情0offer情绪一直很低落硬撑着面了一个岗位岗位有应酬的成分面试的时候hr给我出各种场景题问的问题比较犀利&nbsp;有点压力面的感觉感觉有点回答不上来本来就压抑的情绪瞬间爆发了呢一瞬间特别想哭觉得自己特别没用没绷住掉眼泪了事后想想觉得自己挺有病的&nbsp;真的破大防了
喜欢唱跳rap小刺猬...:我觉得没关系吧,之前有一次面试leader给我压力面,我顶住了压力,结果入职的时候发现组里氛围很差,果断跑路。其实从面试就能大概看出组的情况,面试体验好的组倒是不一定好,但是面试体验不好的组。。。就很难说
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务