32pts 手写堆离奇错误
查看原帖
32pts 手写堆离奇错误
1199534
ycy1124楼主2024/12/28 16:19
#include<bits/stdc++.h>
using namespace std;
struct Node{
    int w,i;
}qwq[500005];
int n,tot;
long long sum=0,js=0;
inline void work(int x){
    if(x*2+1<=tot&&qwq[x*2+1].w>qwq[x].w&&qwq[x*2+1].w>qwq[x*2].w){
        swap(qwq[x*2+1],qwq[x]);
        work(x*2+1);
    }
    else if(x*2<=tot&&qwq[x*2].w>qwq[x].w){
        swap(qwq[x],qwq[x*2]);
        work(x*2);
    }
}
inline void work1(int x){
    if(x!=1&&qwq[x].w>qwq[x/2].w){
        swap(qwq[x],qwq[x/2]);
        work1(x/2);
    }
}
int a[250005],b[250005];
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    tot=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    for(int i=1;i<=n;i++){
        // cout<<tot<<' '<<js<<' '<<sum<<'\n';
        sum+=a[i];
        if(js+b[i]>sum){
            if(b[i]<qwq[1].w&&tot!=0){
                js-qwq[1].w;
                swap(qwq[1],qwq[tot]);
                --tot;
                work(1);
                js+=b[i];
                qwq[++tot]={b[i],i};
                work1(tot);
            }
            else{
                continue;
            }
        }
        else{
            js+=b[i];
            qwq[++tot]={b[i],i};
            work1(tot);
        }
    }
    cout<<tot<<'\n';
    for(int i=1;i<=tot;i++){
        cout<<qwq[i].i<<' ';
    }
    return 0;
}
2024/12/28 16:19
加载中...