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

輸出

複制

No

備注:

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

N N N個怪物,每個打第 i i i個怪要扣 A i A_i Ai​血,打完後可以恢複 B i B_i Bi​血

初始血量 M M M,要求找到一條打怪路線,能打完所有怪物

• N個怪分兩批打
  • 第一批 : 正收益的怪, 優先打扣血少的(反正打完後能恢複更多血)
  • 第二批 : 負收益的怪, 優先打回血多的怪(反正打誰都要扣血,還不如扣少點)

是以得到排序方式:

• 先按收益從大到小排,然後就可以分成左右兩部分(左邊正收益,右邊負收益)
• 對左邊(正收益部分)按 A i A_i Ai​小到大排序
• 對右邊(負收益部分)按 B i B_i Bi​大到小排序
• O ( n ) O(n) O(n)掃一遍能打完最後一個,就輸出 Y e s Yes Yes

注意 : 不開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;
}