题目:给你t个障碍与初始石头的稳定性m,之后给你每个障碍的丧失稳定性的值与恢复稳定性的值,每次撞完障碍后都会丧失稳定性再恢复恢复稳定性的值,问你在这过程中能否石头稳定性一直是大于0的
思路:贪心
把障碍分成两类,一类是恢复稳定性大于丧失稳定性的障碍,这种障碍一开始肯定要多撞才行,尽量把全部利益收集起来再去撞亏损的障碍
另一类就是丧失稳定性大于恢复稳定性的障碍,这种障碍肯定放在最后撞才好让石头稳定性一直大于0
那么问题又来了,对于这两种障碍要怎么排序?
排序方法都是不一致的,对于第一种障碍,要尽量从丧失稳定性小的开始撞起,因为如果一开始撞丧失稳定性大的有可能撞不过就散架了。如果丧失稳定性大的一直撞不过就说明没办法了,就直接输出"No"
而对于第二种障碍,要按回复稳定性大的开始排序,因为你把前面全部能撞的都撞完后稳定性已经累计到最大值了,这时候肯定尽量要回复更多的稳定性才能继续撞下去(一开始是按丧失稳定性与回复稳定性的差值来排导致WA了好几次)(卡85%的样例的应该就是这里被卡了)
AC代码:
#include <iostream>
#include <algorithm>
using namespace std;
struct stone
{
int a,b;
};
stone c[500005];//存回馈稳定性大于丧失稳定性的障碍
stone d[500005];//存回馈稳定性小于等于丧失稳定性的障碍
bool cmp1(stone a,stone b)
{
return a.a<b.a;
}
bool cmp2(stone a,stone b)//按能回复多少排序
{
return a.b-a.a>b.b-b.a;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
long long m;
cin>>n>>m;
int j=0,k=0;
for(int i=0; i<n; i++)
{
int a,b;
cin>>a>>b;
if(b-a>0)
{
c[j].a=a;
c[j++].b=b;
}
else
{
d[k].a=a;
d[k++].b=b;
}
}
sort(c,c+j,cmp1);//回馈稳定性大于丧失稳定性的按丧失稳定性进行排序,从最小开始加
sort(d,d+k,cmp2);
int ok=1;
for(int i=0; i<j; i++)
{
m-=c[i].a;
if(m<0){
ok=0;
break;
}
m+=c[i].b;
}
for(int i=0; i<k; i++)
{
m-=d[i].a;
if(m<0){
ok=0;
break;
}
m+=d[i].b;
}
if(ok)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}
京公网安备 11010502036488号