思路:
贪心
1.很容易想到如果一个障碍会增加稳定性,而一个会减少稳定性(最终结果),那么我们一定会先选择增加稳定性的,如果增加稳定性的都选不了那减少稳定性后就更选不了了。
2.都是增加稳定性时,先选择丧失稳定性最小的那个,这样处理后可以肯定,如果丧失稳定性最小的那个选不了,不管怎样选择它还是选不了。
3.都是减小稳定性时,先选择回馈稳定性最多的那个,比如:
2 40
30 34
40 50
我们肯定先选第二个再选第一个
Code:
#include<bits/stdc++.h> #define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; typedef long long ll; struct node{ int x,y,val; bool operator<(const node&a) const{ if(val>0&&a.val>0) return x<a.x; if(val<0&&a.val<0) return y>a.y; return val>a.val; } }q[500005]; int main() { js; int n,m,a,b,t; cin>>t; while(t--) { cin>>n>>m; for(int i=1;i<=n;++i) { cin>>q[i].x>>q[i].y; q[i].val=q[i].y-q[i].x; } sort(q+1,q+1+n); int flag=1; ll sum=m; for(int i=1;i<=n;++i) { if(q[i].x>sum) { cout<<"No\n",flag=0; break; } sum+=q[i].val; } if(flag) cout<<"Yes\n"; } return 0; }