E题代码有盲区,有无路过的大佬帮忙看一下

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e6+10;
int f[N];
int k[N];
struct node{
    int l;
    int r;
};
vector<node>v;

void sc(int x,int y,int q){
    if(x>y)return;
//     f[x]-=q;
//     f[y]-=q;
    int fff=0;
    if(f[x]-q<=0){
        x++;
        fff=1;
    }
    if(f[y]-q<=0){
        y--;
        fff=1;
    }
    if(fff){
        sc(x,y,q);
        return;
    }
    
    int zc=min(f[x]-q,f[y]-q);
//     cout<<x<<' '<<y<<' '<<zc<<endl;
    for(int i=1;i<=zc;i++){
        cout<<x<<' '<<y<<endl;
    }
    sc(x,y,q+zc);
    return;
    
}

signed main(){
    int n,m;
    cin>>n>>m;
    int su=0;
    int mi=0;
    for(int i=1;i<=n;i++){
        cin>>f[i];
        su+=f[i];
    }
    if(m>su){
        cout<<-1<<endl;
        return 0;
    }
    int flag=1;
    int q=0;
    int dql=1;
    for(int i=1;i<=n;i++){
        if(f[i]>=f[i-1]){
            if(flag){
                q=i;
            }else{
                if(f[i]==f[i-1])continue;
                mi+=f[q];
                v.push_back({dql,i-1});
                k[q]=1;
                q=i;
                dql=i;
                flag=1;
            }
        }else{
            flag=0;
        }
    }
    mi+=f[q];
    v.push_back({dql,n});
    k[q]=1;
//     cout<<mi<<endl;
    if(m<mi || m>su){
        cout<<-1<<endl;
        return 0;
    }
//     for(node dq:v){
//         cout<<dq.l<<' '<<dq.r<<endl;
//     }
    int c=m-mi;
    for(node dq:v){
        int dl=dq.l;
        int dr=dq.r;
        for(int i=dl;i<=dr;i++){
            if(k[i]==1)break;
            int dc=min(f[i],c);
            for(int j=1;j<=dc;j++){
                cout<<i<<' '<<i<<endl;
            }
            f[i]-=dc;
            c-=dc;
            if(c==0)break;
        }
        for(int i=dr;i>=dl;i--){
            if(k[i]==1)break;
            int dc=min(f[i],c);
            for(int j=1;j<=dc;j++){
                cout<<i<<' '<<i<<endl;
            }
            f[i]-=dc;
            c-=dc;
            if(c==0)break;
        }
        if(c==0)break;
    }
    
    for(node dq:v){
        int dl=dq.l;
        int dr=dq.r;
        sc(dl,dr,0);
    }
    return 0;
    
    
}

全部评论

相关推荐

牛客78682892...:直接点还好,总比要了简历也不回的强
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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