题解 | #「土」巨石滚滚#

额……看到大家都在分类讨论，分享一个懒得分类讨论的办法吧。

考虑两个相邻的障碍物AB，前后都已经排好了。假设土球滚到A前时稳定性为x,想要通过AB需要x-A.a>=0且x-A.a+A.b-B.a>=0;变形一下x>=A.a;x>=A.a-A.b+B.a。也就是说，通过AB需要一个“门槛”max(A.a,A.a-A.b+B.a)。如果说排列AB比BA更优，意味着通过AB比通过BA所需的门槛更低，即max(A.a,A.a-A.b+B.a)<max(B.a,B.a-B.b+A.a)。这就是通用的比较函数了，分析一下会发现其实跟大家分类讨论的排序是一样的，个人感觉理解起来会更容易一些。 PS：记得开long long，老是在这种地方踩坑我也是够了……

#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
long long t, n, m;
bool cmp(pair<int, int> x, pair<int, int> y) {
    return max(x.first, x.first - x.second + y.first) < max(y.first, y.first - y.second + x.first);
}
int main() {
    cin >> t;
    while (t--) {
        cin >> n >> m;
        vector<pair<int, int>> a(n);
        for (int i = 0;i < n;i++) {
            cin >> a[i].first >> a[i].second;
        }
        sort(a.begin(), a.end(), cmp);
        string ans = "Yes";
        for (auto x : a) {
            if (m < x.first) {
                ans = "No";
                break;
            }
            m -= x.first;
            m += x.second;
        }
        cout << ans << endl;
    }
    return 0;
}