NC53681 「土」巨石滚滚(贪心)

NC53681「土」巨石滚滚
题目描述
帕秋莉掌握了一种土属性魔法
她使用这种魔法建造了一个大型的土球，并让其一路向下去冲撞障碍
土球有一个稳定性x，如果x < 0，它会立刻散架
每冲撞一个障碍，土球会丧失ai的稳定性，冲撞之后，又会从障碍身上回馈bi的稳定性
帕秋莉想知道，如果合理的安排障碍的顺序，在保证土球不散架的情况下，是否可以将障碍全部撞毁呢？
输入描述
输入一个整数T，代表T组数据，每组数据中：
前一行两个整数n , m，表示障碍个数和土球的稳定性
接下来一行两个整数，分别表示障碍的ai和bi
输出描述
若可以，输出“Yes”(不含引号)，否则输出“No”(不含引号)
输入样例
1
5 50
49 49
52 0
5 10
26 24
70 70
输出样例
No
思路：
这题。。。。很显然的贪心。。但是无论我怎么设计贪心总是有东西没考虑到。。看了大佬的思路，大佬提供了一种考虑很周全的思路。分段贪心。对于每个 $a, b$ ，我们可以求一下它的增量 $△$ $x$ 。然后对增量以 $0$ 为中点分段，我们先对增量降序，对于 $△ x > 0$ 的部分我们一定可以使得 $m$ 变得更大，但是有可能 $a > m$ 会使得 $m$ 得不到最优值，我们需要对 $△ x > 0$ 这部分的 $a$ 升序，对于 $△ x < 0$ ，这一部分我们已经拿不到额外的利益了，为了使得 $m$ 最优，我们要让 $a$ 尽可能的小， $b$ 尽可能大，所以对于 $△ x < 0$ 部分对 $b$ 降序就好了。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 10;
typedef long long int ll;

struct node{
	ll x,y,z;
	node(){}
	node(ll a,ll b,ll c = 0):x(a),y(b),z(b - a){}
};
node a[maxn];
bool cmp(node a,node b){
	return a.z > b.z;
}
bool cmp1(node a,node b){
	return a.x < b.x;
} 
bool cmp2(node a,node b){
	return a.y < a.y;
}
void solved(){
	int t;cin>>t;
	while(t--){
		ll n,m;cin>>n>>m;
		int cnt = 0;
		for(int i = 1; i <= n; i++){
			ll x,y;cin>>x>>y;
			a[i].x = x;a[i].y = y;
			a[i].z = y - x;
			if(a[i].z > 0)cnt++;
		}
		if(cnt == n){
			cout<<"Yes"<<endl;continue;
		}
		sort(a + 1,a + 1 + n,cmp);
		sort(a + 1,a + 1 + cnt,cmp1);
		sort(a + 1 + cnt,a + 1 + n,cmp2);
		for(int i = 1; i <= n; i++){
			m -= a[i].x ; 
			if(m < 0)break;
			m += a[i].y;
		}
		if(m > 0)cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
}
int main(){
	solved();
	return 0;
}