题目描述

帕秋莉掌握了一种土属性魔法

她使用这种魔法建造了一个大型的土球，并让其一路向下去冲撞障碍

土球有一个稳定性x，如果x < 0，它会立刻散架

每冲撞一个障碍，土球会丧失ai的稳定性，冲撞之后，又会从障碍身上回馈bi的稳定性

帕秋莉想知道，如果合理的安排障碍的顺序，在保证土球不散架的情况下，是否可以将障碍全部撞毁呢？

输入描述: 

输入一个整数T，代表T组数据，每组数据中：
前一行两个整数n , m，表示障碍个数和土球的稳定性
接下来一行两个整数，分别表示障碍的ai和bi

输出描述: 

若可以，输出“Yes”(不含引号)，否则输出“No”(不含引号)
示例1

输入 

1
5 50
49 49
52 0
5 10
26 24
70 70

输出 

No

备注: 

Σn <= 500000, 1<=m<=100000,0<=a,b<=100000

思路

一道贪心题，关键是写好排序规则。如果两个都是回复的，那么把那个伤得少的排在前面，否则可能没命去吃后面回复的了。如果两个都是损伤的，那选回复得多的，搏一搏是吧，反正都是死。如果一个损伤一回复，肯定把回复的放在前面先苟一手对吧。注意生命值开long long因为可能疯狂回疯狂回爆int！！！(80%)

代码 

//「土」巨石滚滚(思维 贪心) 
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N = 5000010;

struct S
{
	int a;
	int b;
	
	bool operator < (const S t)const 
	{
		if(b > a && t.b > t.a)
			return a < t.a;
		if(b < a && t.b < t.a)
			return b > t.b;
		return b - a > t.b - t.a;
	} 
};

S s[N];

int main()
{
 	int t , i;
 	scanf("%d" , &t);
 	while(t--)
 	{
		ll n , x;
		scanf("%lld %lld" , &n , &x);
		for(int i = 0 ; i < n ; i++)
			scanf("%d %d" , &s[i].a , &s[i].b);
		
		sort(s , s + n);
		for(i = 0 ; i < n ; i++)
		{
			x -= s[i].a;
			if(x < 0)
				break;
			x += s[i].b;
		} 
	 	
	 	printf("%s\n" , i == n ? "Yes" : "No");
	}
	return 0; 
}