U314854 打怪兽
链接
出题人: FallingSakura
没什么技术含量,但是出这道题的测试点真的很烦。
精心设计的随机算法随机了好几百次也只有两个能把我错误的代码卡掉。
因此本题计分方式为最小值计分,即你必须AC全部测试点。
问题描述
有只怪兽,初始你有点血量,打第只怪兽需要的血量,打完第只怪兽会获得的血量,你可以按照任意次序打所有怪兽,问能否打完所有的怪兽,打完后你剩多少血量,并给出一种方案。
思路
对于赚血的怪来说,我们按照升序打,避免我们打不过。
而对于亏血的怪来说,我们按照亏血的多少来打?
显然不可以,万一打这只怪的门槛很高,打了这只就没法打其它的了。
我们想,到最后我们的血量都一定是固定的(可以为负值),那么我们不妨反过来看,从打完后的血,一直把打过的怪“撤销”,那么亏血的怪就相当于赚血的怪了,那么我们就可以按照一样的策略来打这些怪了,反向时,即按照升序打,而反过来,就变成了降序打。
那么这道题就做完了。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
const int M=2e5+7;
int n,k;
int a[N],b[N];
struct mon{
int a,b,id;
}m[M];
bool cmp(mon x,mon y)
{
if((x.b-x.a>0)&&(y.b-y.a>0)) return x.a<y.a;
else if(x.b-x.a>0) return true;
else if(y.b-y.a>0) return false;
return x.b>y.b;
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&m[i].a,&m[i].b);
m[i].id=i;
}
sort(m+1,m+1+n,cmp);
int i=1;
for(;i<=n;i++)
{
if(k>=m[i].a)
{
if(m[i].b-m[i].a>=0) k+=m[i].b-m[i].a;
else break;
}
else
{
cout<<"No";
return 0;
}
}
if(i==n)
{
cout<<"Yes"<<endl;
return 0;
}
for(;i<=n;i++)
{
if(k>=m[i].a)
{
k+=m[i].b-m[i].a;
}
else
{
cout<<"No";
return 0;
}
}
cout<<"Yes"<<endl;
cout<<k<<endl;
for(int i=1;i<=n;i++)
{
printf("%d ",m[i].id);
}
return 0;
}