思路
冲撞障碍物后有两个可能,增加稳定型 or 减少稳定性,所以分两种情况分析
1、靠常识我们会先撞增加稳定性的障碍物,增加稳定性的当然是要先撞a小的,因为后面可能有a很大的,目前的稳定性可能不够,需要打小怪升级一下,如果直接撞可能会散架。
2、接下来就是撞稳定性减少的,因为必须全部撞完所有的障碍物,所以这里受到的伤害是一个定值 那要如何保证不那么任意散架呢,当然是回复力( )更大的在前面更好,先吃到更多的回复才有能力撞下一个
代码
#include<bits/stdc++.h> using namespace std; inline ll read(){ ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); } while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return s * w; } struct node{ int a,b; bool operator < (const node n) const{ if(b >= a && n.b >= n.a) return a < n.a;//都会回复选a小 if(b >= a) return true;//否则选会回复的 if(n.b >= n.a) return false; return b > n.b;//撞后都不回复选回复最大的 } }q[500005]; int main(){ int t = read(); while(t--){ ll n = read(),m = read(); for(int i = 0 ; i < n ; ++i){ q[i].a = read(); q[i].b = read(); } sort(q,q+n); bool flag = true; for (int i = 0; i < n; i++){ if(m < q[i].a){ flag = false; break; } m += (q[i].b - q[i].a); } if(flag) puts("Yes"); else puts("No"); } }