这题就是一个简单的贪心 + 排序问题,看到题目,应该可以想到要把石块分成收益大于消耗和收益小于消耗两类。
显然第一类收益大于消耗的石头要先撞,是自己变得更加牢固后再去撞另一类,然后我们想,要使自己确保在第一类中尽可能撞的多,就要 a(损耗)小的先撞,因为后面可能有a很大的,目前的稳定性可能不够,需要先让自己稳定性变大,如果直接撞a大的可能会散架。
第二类每次撞都会使自己的稳定性变差,所以我们考虑先撞b(收益)更大的,保证自己尽可能不会散架,(这里注意不能先撞自身消耗小的,举个反例:开始m=50, a[1] = 30, b[1] = 28; a[2] = 49, b[2] = 42;如果先撞自身消耗小的,就是先撞1号石头,之后自身的稳定性为48,无法再撞2号石头,显然如果先撞2号石头是可以把所有的石头撞完的)
献上本蒟蒻的代码
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define endl '\n'
#define int long long
#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
const int N = 5e6 + 7;
const int M = 5e5 + 7;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
struct node {
int a, b, c; // a为消耗,b为收益,c = b - a
}num[M];
bool cmp(node x, node y) { //重载排序
if(x.c >= 0 && y.c >= 0 && x.a != y.a) return x.a < y.a;
if(x.c >= 0 && y.c < 0) return 1;
if(x.c < 0 && y.c >= 0) return 0;
return x.b > y.b;
}
signed main() { ios;
int t; cin >> t;
while(t--) {
memset(num, 0, sizeof num);
int n, m; cin >> n >> m;
for(int i = 1; i <= n; ++i) { cin >> num[i].a >> num[i].b; num[i].c = num[i].b - num[i].a; }
sort(num + 1, num + n + 1, cmp);
bool flag = 1;
for(int i = 1; i <= n; ++i) {
if(m < num[i].a) { flag = 0; break; }
m += num[i].c;
}
flag ? cout << "Yes" : cout << "No";
cout << endl;
}
return 0;
} 
京公网安备 11010502036488号