题目链接:https://ac.nowcoder.com/acm/contest/2272/H
题目大意:
思路:我们先统计净增加量,那么对于增加量>0的情况,肯定是以a[i]越小在前面。
对于增加量<0的情况。我们以b[i]排降序。

证明:s为达到这块石头前的最小耐力。

并且得到一个附加证明:净增加量<0的情况。除了B[n]取最小值。其他的怎样排序没有影响。

#include <bits/stdc++.h>
#define LL long long
using namespace std;

struct node{
    LL a, b, c;
}a[500005];

int cmp(node &a, node &b){
    if(a.c>=0&&b.c>=0){
        return a.a<b.a;
    }
    else if(a.c<0&&b.c<0){
        return a.b>b.b;
    }
    else{
        return a.c>b.c;
    }
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--){
        LL n, m;
        scanf("%lld%lld", &n, &m);
        for(int i=1; i<=n; i++){
            scanf("%lld%lld", &a[i].a, &a[i].b);
            a[i].c=a[i].b-a[i].a;
        }
        sort(a+1, a+1+n, cmp);
        for(int i=1; i<=n; i++){

            m-=a[i].a;
            if(m<0){
                break;
            }
            else{
                m+=a[i].b;
            }
        }
        if(m>=0){
            printf("Yes\n");
        }
        else{
            printf("No\n");
        }
    }

    return 0;
}