题解19 巨石滚滚

思路&AC代码：

#include<iostream>
#include<algorithm>
using namespace std;
long long m;//一开始我还以为m<=100000不会溢出，却忘了万一全是正收入组且每个都收入100000呢？结果可达到1e5+5e5*1e5超过2e9(int),而在32位系统long ~=int，所以用long long
int n,cnt;
struct ty
{
    int lose,resume,delta;
}a[500010];
bool comp1(const ty &a, const ty &b)
{
    return a.delta>b.delta;//把递增的筛出来
}
bool compg(const ty &a, const ty &b)
{
    return a.lose<b.lose;//形象的比喻：一开始打小怪提升自身等级，一边升级一边去打更大的怪
}
bool compb(const ty &a, const ty &b)
{
    return a.resume>b.resume;//在稳定度递减时，最容易失败的就是在撞倒一次障碍，回复一次，再撞倒之时，这是要让三者加起来的损失最少，即lose1−resume1+lose2≤lose2-resume2+lose1，解得resume1>=resume2
}
bool deal()
{   
    //下面这三行其实是感性判断，仍需理性验证
    sort(a+1, a+1+n, comp1);//把递增的筛出来。递增的排前面，使得后面递减之前积累足够的稳定性
    sort(a+1, a+1+cnt, compg);//按照适用于递增的规则排序
    sort(a+1+cnt, a+1+n ,compb);//按照适用于递减的规则排序
    for(int i=1; i<=n ;i++)
    {
        if(m-a[i].lose>=0/*其实改成m>=a[i].lose更好，防止负数溢出，但依照题目条件确实不会溢出*/) {m=(m-a[i].lose) +a[i].resume;}
        else {return false;}
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int t;cin>>t;
    int tlose,tresume;
    while(t--)
    {
        cnt=0;
        cin>>n>>m;
        for(int i=1; i<=n; i++)
        {
            cin>>tlose>>tresume;
            a[i].lose=tlose;a[i].resume=tresume;
            a[i].delta=tresume-tlose;
            if(a[i].delta>=0) {cnt++;}
        }
        bool res=deal();
        if(res) {cout<<"Yes\n";}
        else {cout<<"No\n";}
    }
}