BZOJ 3709(思维，贪心)比较经典的一种思维题
「土」巨石滚滚
https://ac.nowcoder.com/acm/contest/2272/H
洛谷链接(输出稍有不同) ：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;
} 
Momenta公司福利 554人发布
查看30道真题和解析