看这题,就是贪心。贪心怎么贪??就不误导了;分成两类,一种是b-a>=0的;另一种是b-a<0;对于第一种,显而易见,要按照a升序排列;对第二种,
需要按照b降序排列,因为对于第二种,无论怎么排,m的值一定是减小的。所以先选b大的;
#include<bits/stdc++.h> using namespace std; #define ll long long ll t,n,m; struct node{ ll a,b; }nod[55000]; node no[55000]; bool comp(node x,node y) { return x.a<y.a; } bool cmp(node x,node y) { return x.b>y.b; } int main() { cin>>t; while(t--) { memset(nod,0,sizeof(nod)); memset(no,0,sizeof(no)); cin>>n>>m; int cnt=0,cnt1=0; for(int i=1;i<=n;i++) { int x,y; cin>>x>>y; if(y-x>=0) nod[++cnt].a=x,nod[cnt].b=y; else no[++cnt1].a=x,no[cnt1].b=y; } sort(nod+1,nod+1+cnt,comp); sort(no+1,no+1+cnt1,cmp); int ok=0; for(int i=1;i<=cnt;i++) if(m>=nod[i].a) m+=nod[i].b-nod[i].a; else {ok=1;break;} for(int i=1;i<=cnt1;i++) if(m>=no[i].a) m+=no[i].b-no[i].a; else {ok=1;break;} if(!ok) cout<<"Yes"<<endl; else cout<<"No"<<endl; } }