这题就是一个简单的贪心 + 排序问题,看到题目,应该可以想到要把石块分成收益大于消耗和收益小于消耗两类。
显然第一类收益大于消耗的石头要先撞,是自己变得更加牢固后再去撞另一类,然后我们想,要使自己确保在第一类中尽可能撞的多,就要 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; }