题目

题目描述：
帕秋莉掌握了一种土属性魔法
她使用这种魔法建造了一个大型的土球，并让其一路向下去冲撞障碍
土球有一个稳定性x，如果x < 0，它会立刻散架
每冲撞一个障碍，土球会丧失ai的稳定性，冲撞之后，又会从障碍身上回馈bi的稳定性
帕秋莉想知道，如果合理的安排障碍的顺序，在保证土球不散架的情况下，是否可以将障碍全部撞毁呢？

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

输出描述：
若可以，输出“Yes”(不含引号)，否则输出“No”(不含引号)

解析

这道题的题不难看懂，可我还是看错了，没看到要排序。。。
  • 题目意思就是排个序使土球尽量有可能撞完所有石头。

所以这道题非常明显就是一道贪心问题，那我们来讨论贪心策略：
  1. 首先我们知道，贪心肯定贪心在排序上面，我们在排序上面可以怎么贪呢？无非与a和b有关。
  2. 然后要注意一点就是，我们是先对球损坏a，再修复b，如果损坏了a就使稳定性变成负数了，就结束了。
  3. 所以我们现在的贪心要素有：a的损坏大小，b的修补大小。
  4. 在看到这里我们发现，a和b没有大小之分，所以我们在撞了石头之后，稳定性还有可能反而升高了。
    所以我们毫无疑问的将可以升高稳定性的排在前面
    （为什么不升高稳定性的不能在前面呢？因为如果在连升高的时候都能撞烂了，那降低了之后就更容易烂掉了）。
  5. ————————————————————分ger线————————————————————
  6. 然后我们数组就分成了两个部分：前面是稳定性升高（包括不变）的，后面是稳定性降低的。然后我们就要考虑，这两块里面怎么排。
  7. 也许你会觉得这两块都没啥必要排了，但其实这个排序很重要。
  8. 稳定性升高内部排序规则：虽然每个都可以让稳定性升高，但是我们还要考虑在升高的过程中这个球会不会烂掉！！
    这个时候就可能出现，在某一次损坏下，我们这个球会烂掉，但是假如别的撞后不会烂的球帮它升高之后，就不会撞烂了的情况。
    所以：我们的排序就应该有这一点：按照损坏程度大小，从小到大排序（也就是在为下一个球的情况做贡献）。
  9. 稳定性降低内部排序规则：这个时候我们不应该考虑自己这个球会不会烂掉，因为该烂掉总会烂掉。但我们要保证下一个更不容易烂掉。
    所以我说的：不用在乎自己的意思是，如果我的破坏值已经很大了，怎么换都没有意义，一样会烂掉。
    然后我说的要为下一个球考虑就是：让下一个的时候，我们的稳定性能更高，也就是这一个的回复值要更大。
    所以我们的排序就应该有这一点：按照恢复程度的大小，从大到小排序（让下一个有更多空间去破坏）。

然后就是怎么操作的问题了对吧：
  1. 我们在这里用到一个方便的就是STL库里面的sort函数。我们这里阔以写一个cmp函数，也可以重载运算符。
  2. 我在这里是重载运算符，因为这样可以大幅提高排序效率（两个写起来是一样的）。
  3. 因为我们在这里有两个因素：a的损坏大小，b的修补大小。所以就有四种情况（我们假设在数组里面靠前面的是u，靠后面的是v）。
  4. <1>假如u，v稳定性都升高，我们按照损坏程度升序排序： 
    if (a <= b && v.a <= v.b) return a < v.a;
  5. <2>假如u稳定性升高，v稳定性降低，我们顺序不用变（因为稳定性升高的要在前面）： 
    if (a <= b && v.a > v.b) return true;
  6. <3>假如u稳定性降低，v稳定性升高，我们交换顺序（理由同上）： 
    if (a > b && v.a <= v.b) return false;
  7. <4>假如u，v稳定性都降低，我们按照修补程度降序排序： 
    if  (a  >  b  &&  v.a  >  v.b)  return b > v.b;

打代码咯：
  1. 输入数组。
  2. 排个序咯。
  3. 然后循环遍历，判断是否会挂（损坏的时候是否耐久度小于0），用flag标记。
  4. 看我代码咯~

AC代码 

#include <iostream> 
#include <algorithm>
#include <cstdbool>
using namespace std; 
typedef long long ll;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); 

//代码预处理区

const int MAX = 5e5 + 7; 
struct Node {
    int a, b;
    bool operator < (const Node& v) const {
        if (a <= b && v.a <= v.b) return a < v.a;
        //如果两个都可以增加，先增加消耗小的（让后面消耗大的回复块有机会）
        if (a <= b && v.a > v.b) return true;
        if (a > b && v.a <= v.b) return false;
        //如果一个可以增加，另一个不可以，就让可以增加的在前面
        if  (a  >  b  &&  v.a  >  v.b)  return b > v.b;
        //剩下的就是都不能增加的情况，就让回复多的先
    }
} stone[MAX];
//全局变量区 

int main() {
    IOS;
    int T; cin >> T;
    while (T--) {
        ll n, m; cin >> n >> m;
        for (int i = 1; i <= n; i++)
            cin >> stone[i].a >> stone[i].b;
        sort(stone + 1, stone + 1 + n);
        bool flag = true;//flag=1表示石头没散架
        for (int i = 1; i <= n && flag; i++)
            if (m - stone[i].a < 0) flag = false;
            else m -= stone[i].a - stone[i].b;
        cout << (flag ? "Yes" : "No") << endl;
    }
    return 0; 
}
//函数区