60pts求hack
查看原帖
60pts求hack
1199534
ycy1124楼主2024/12/21 09:15
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct Node{
    int x,y;
}a[150005],b[300005];
inline bool cmp(Node x1,Node x2){
    return x1.y<x2.y;
}
int tot,n;
inline void work(int x){
    if(b[x].x>b[x/2].x){
        swap(b[x],b[x/2]);
        work(x/2);
    }
}
inline void work1(int x){
    if(x*2+1<=tot&&b[x].x<b[x*2+1].x&&b[x*2+1].x>b[x*2].x){
        swap(b[x],b[x*2+1]);
        work1(x*2+1);
    }
    else if(x*2<=tot&&b[x].x<b[x*2].x){
        swap(b[x],b[x*2]);
        work1(x*2);
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
    }
    sort(a+1,a+n+1,cmp);
    int js=0,ans=0;
    for(int i=1;i<=n;i++){
        // cout<<js<<' '<<js+a[i].x<<' '<<a[i].y<<'\n';
        if(js+a[i].x<=a[i].y){
            b[++tot]=a[i];
            js+=a[i].x;
            work(tot);
            ++ans;
        }
        else if(a[i].x<b[1].x){
            swap(b[1],b[tot]);
            js-=b[tot].x;
            --tot;
            work1(1);
            b[++tot]=a[i];
            js+=a[i].x;
            work(tot);
        }
        // cout<<js<<'\n';
    }
    cout<<ans;
    return 0;
}
2024/12/21 09:15
加载中...