洛谷链接(输出稍有不同) :https://www.luogu.com.cn/problem/P4025
其实是老生常谈,放在这防止脑子生锈
分析 : 每一次冲撞,先消耗a,后恢复b,冲撞的总收获c=b-a。考虑所有的冲撞,分两批完成,第一批是收获>=0的,完成第一批后做第二批,收获<0的。
接下来考虑同一批中的内部顺序,对第一批,按a升序排列(以防某一步a太大,m-a<0)。
对第二批,不管最终排序如何,最终的m值是确定的(如果能完成全部冲撞)。倒序来看,即分析逆过程。之前每次冲撞先消耗a,再恢复b,逆过程为先增加b后消耗a,所以逆推应当按照b升序排列,那么正推就该是按b降序排列。
code :
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 5e5 + 5; struct Node { ll a,b,c; }pp[maxn]; bool cmp(const Node &A,const Node &B) { if(A.c>=0&&B.c<0) return true; if(A.c<0&&B.c>=0) return false; if(A.c>=0&&B.c>=0) return A.a<B.a; return A.b>B.b; } int main() { int t; scanf("%d",&t); while(t--) { int n,flag=0; ll m; scanf("%d%lld",&n,&m); for(int i=1;i<=n;i++) scanf("%lld%lld",&pp[i].a,&pp[i].b),pp[i].c=pp[i].b-pp[i].a; sort(pp+1,pp+1+n,cmp); for(int i=1;i<=n;i++) { if(m<pp[i].a) { flag=1; break; } m+=pp[i].c; } if(!flag) printf("Yes\n"); else printf("No\n"); } return 0; }