欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2019蓝桥杯B组第10题:灵能传输

程序员文章站 2022-04-30 09:25:16
...

题目描述:灵能传输

2019蓝桥杯B组第10题:灵能传输

2019蓝桥杯B组第10题:灵能传输

2019蓝桥杯B组第10题:灵能传输


思路

挺难的一道贪心题,思路很难很难想。

主要时用了 前缀和+贪心 的思想

具体的我就不讨论了,大家看视频

还是老师讲的比较清楚

代码

#include<iostream> 
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long ll;
const int maxn = 3e5+10;
ll s[maxn]; 
ll a[maxn];
bool vis[maxn];
int main(){
    int t;scanf("%d",&t);
    while(t--){
        memset(s,0,sizeof(s));
        memset(vis,0,sizeof(vis));
        int n;scanf("%d",&n);
        for(int i = 1;i<=n;i++){
            scanf("%lld",&s[i]);
            s[i]+=s[i-1];// 计算总和
        }
        ll s0 = s[0],sn=s[n];
        if(s0>sn) swap(s0,sn);
        sort(s,s+n+1);// 排序记得0
        for(int i = 0;i<=n;i++){
            if(s[i]==s0){
                s0=i;
                break;
            }
        }
        for(int i = n;i>=0;i--){
            if(s[i]==sn){
                sn = i;
                break;
            }
        }
        
        int l = 0,r = n;
        for(int i = s0;i>=0;i-=2){
            a[l++]=s[i];
            vis[i]=1;
        }
        for(int i = sn;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 ans = 0;
        for(int i = 1;i<=n;i++){
            ans = max(ans,abs(a[i]-a[i-1]));
        }
        printf("%lld\n",ans);
    }
    return 0;
}