思路:
贪心
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;
} 
京公网安备 11010502036488号