这题一直没有想到一个完备的证明方法,直到了看到了一篇博客
首先如果撞了能加防御值,一定放在前面,也就是说分成两类,撞了之后加防御的,这一部分按照破坏值排序即可,
因为要尽量把防御值增加到最大才更可能撞大的
第二种情况 对于一个顺序,改变其中两个的位置,对其他的不造成影响,所以只考虑 a和b 如果ab可以ba也可以就不用考虑,ab和ba都不可以也不用考虑,只剩下了ab可以ba不可以
图片说明
第二行和第四行合并可以得到a.升>b.升
也就得到了排序方法

#include<iostream>
#include<algorithm>
using namespace std;
int t,n;
long long m;
struct node
{
    int div,add,all;
}a[500010];
bool cmp(node a,node b)
{
    if(a.all>=0&&b.all>=0)return a.div<b.div;
    if(a.all>=0&&b.all<0)return true;
    if(a.all<0&&b.all>=0)return false;
    return a.add>b.add;
}
int main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        int f=0;
        for(int i=1;i<=n;i++)
            cin>>a[i].div>>a[i].add,a[i].all=a[i].add-a[i].div;
        sort(a+1,a+1+n,cmp);
        for(int i=1;i<=n;i++)
        {
            m-=a[i].div;
            if(m<0)
            {f=1;
                cout<<"No"<<endl;
                break;
            }
            m+=a[i].add;
        }
        if(f==0)cout<<"Yes"<<endl;
    }
}