1 条题解
-
0
#include<bits/stdc++.h> using namespace std; const int N=1000005; int n,ans,m; long long x,f[N],s[N]; priority_queue<int>q; struct st { long long d,s; } a[N]; bool cmp(const st x,const st y) { if(x.d*y.d<=0) return x.d>y.d; else return max(x.s-x.d,y.s-x.d-y.d)<max(y.s-y.d,x.s-y.d-x.d); } void solve() { memset(f,0,sizeof f),cin>>n>>x,ans=0; for(int i=1; i<=n; ++i) cin>>a[i].d>>a[i].s; sort(a+1,a+1+n,cmp),a[n+1].d=-1; int k1=0,k2=n+1; long long w=0; for(int i=1; i<=n; ++i) { if(a[i].d>0&&a[i+1].d<=0) k1=i; if(a[i].d<0&&a[i-1].d>=0) k2=i; s[i]=s[i-1]+a[i].d; } for(int i=k1+1; i<k2; ++i) ans+=s[i]+x>=a[i].s; while(!q.empty()) q.pop(); for(int i=k1; i>=1; --i) { if(w+s[i]+x>=a[i].s) ++ans,q.push(a[i].d); else { q.push(a[i].d); w+=q.top(); q.pop(); } } while(!q.empty()) q.pop(); x=s[n]+x,w=0; s[n+1]=0; for(int i=n;i>=k2;--i) s[i]=s[i+1]-a[i].d; for(int i=k2; i<=n; ++i) { if(w+s[i+1]+x>=a[i].s) ++ans,q.push(-a[i].d); else { q.push(-a[i].d); w+=q.top(); q.pop(); } } cout<<ans<<endl; } int main(){ ios::sync_with_stdio(0),cin.tie(0); int T; cin>>T; while(T--) solve(); return 0; }
信息
- ID
- 279
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者