NC53681 土巨石滚滚贪心

链接：https://ac.nowcoder.com/acm/problem/53681
来源：牛客网

题目描述

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

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

土球有一个稳定性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

输出
复制

备注:

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

$N$ 个怪物,每个打第 $i$ 个怪要扣 $A_{i}$ 血,打完后可以恢复 $B_{i}$ 血
初始血量 $M$ ,要求找到一条打怪路线,能打完所有怪物

N个怪分两批打
- 第一批 : 正收益的怪, 优先打扣血少的(反正打完后能恢复更多血)
- 第二批 : 负收益的怪, 优先打回血多的怪(反正打谁都要扣血,还不如扣少点)

所以得到排序方式:

先按收益从大到小排,然后就可以分成左右两部分(左边正收益,右边负收益)
对左边(正收益部分)按 $A_{i}$ 小到大排序
对右边(负收益部分)按 $B_{i}$ 大到小排序
$O (n)$ 扫一遍能打完最后一个,就输出 $Y e s$

注意 : 不开long long 死光光

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif


#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>
#define MAXN (500005)
#define ll long long int
#define INF (0x7f7f7f7f)
#define int long long int
#define QAQ (0)

using namespace std;

#ifdef debug
#define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0)
void err() { cout << "\033[39;0m" << endl; }

template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#endif

int n, m, Q, K, an, bn; 

/** * 分两批撞: * 第一批 : 撞正收益的 优先撞花费小的 * 第二批 : 撞负收益的 优先撞回血大的 */
struct Node {
	int x, y, w;
} a[MAXN];

bool cmp1(Node& noa, Node& nob) { //按收益
	return noa.w > nob.w;
}

bool cmp2(Node& noa, Node& nob) { //正收益 优先撞花费小的
	return noa.x < nob.x;
}

bool cmp3(Node& noa, Node& nob) { //负收益 优先撞回血多的
	return noa.y > nob.y;
}

signed main() {
#ifdef debug
	freopen("test", "r", stdin);
	clock_t stime = clock();
#endif
	scanf("%lld ", &Q);
	while(Q--) {
		scanf("%lld %lld ", &n, &m);
		an = bn = 0;
		for(int i=1; i<=n; i++) {
			scanf("%lld %lld ", &a[i].x, &a[i].y);
			a[i].w = a[i].y - a[i].x;
			if(a[i].w >= 0) an ++;
		}
		sort(a+1, a+1+n, cmp1);
		sort(a+1, a+1+an, cmp2);
		if(an+1 < n)
			sort(a+1+an+1, a+1+n, cmp3);
		bool ok = true;
		for(int i=1; i<=n && ok; i++) {
			if(m < a[i].x) ok = false;
			m += a[i].w;
		}
		printf("%s\n", ok ? "Yes" : "No");
	}



#ifdef debug
	clock_t etime = clock();
	printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
	return 0;
}