题意:
有两个怪兽a和b,血量分别为hpa hpb,攻击力分别为atka atkb
有一个英雄,在第i秒的攻击力为i
每一秒,英雄先受到活着的怪兽攻击力之和的伤害
然后选择一个怪兽攻击
问英雄最少受到多少伤害后才能打死两只怪兽
并输出字典序最小的攻击方案
受到伤害最少的方案一定是先以打死其中一只怪兽为目标,而不是两只怪兽一会儿打一个
但是有可能会在打死目标怪兽之前去打几次另一个怪兽
假设英雄在n秒之后打死两只怪兽,那么n满足1+2+3+……+n>=hpa+hpb的最小的n
因为一定存在一种方案,可以在某一秒不浪费攻击力的恰好打死一只怪兽
然后考虑字典序最小的方案
如果目标是先打死a
从第1秒开始一直打a,假设在第x秒打死a
1、如果从第x+1到第n秒的伤害足够打死b,那么就是先一直打a,a死亡后再去打b
2、如果从第x+1到第n秒的伤害不能打死b,说明第x秒的攻击力打a有浪费。如果浪费了y的攻击力,第y秒去打b即可。所以就是先一直打a,第y秒打b,然后继续打a,a死亡后打b
如果目标是先打死b
从第1秒开始一直打b,假设在第x秒打死b
第x秒浪费的攻击力为y,将这y点攻击力尽可能多地在前面用于打a
即将第1,2,……k,(k满足1+2+……+k<=y的最大的k)秒都改为打a
1、如果前k秒的攻击力,加上第x+1到n秒的攻击力能够打死a,就是前k秒打a,再一直打死b,最后再把a打死
2、如果前k秒的攻击力,加上第x+1到n秒的攻击力不能打死a,假设此时还缺z的攻击,让第k秒打b,第k+z秒打a。所以是第1到k-1秒打a,第k到k+z-1秒打b,第k+z秒打死a,最后打死b
#include<cstdio> #include<algorithm> using namespace std; int sum[64001]; char ans1[64001],ans2[64001]; int main() { for(int i=1;i<=64000;++i) sum[i]=sum[i-1]+i; int T,hpa,hpb,ata,atb; int s,n; int f,rest,ff,rr; long long hp1,hp2; scanf("%d",&T); while(T--) { scanf("%d%d%d%d",&hpa,&hpb,&ata,&atb); s=hpa+hpb; n=lower_bound(sum+1,sum+64001,s)-sum; f=lower_bound(sum+1,sum+64001,hpa)-sum; hp1=0; for(int i=1;i<=f;++i) { ans1[i]='A'; hp1+=ata+atb; } for(int i=f+1;i<=n;++i) { ans1[i]='B'; hp1+=atb; } if(sum[n]-sum[f]<hpb) { rest=sum[f]-hpa; ans1[rest]='B'; } f=lower_bound(sum+1,sum+64001,hpb)-sum; hp2=0; for(int i=1;i<=f;++i) { ans2[i]='B'; hp2+=ata+atb; } for(int i=f+1;i<=n;++i) { ans2[i]='A'; hp2+=ata; } rest=sum[f]-hpb; ff=upper_bound(sum+1,sum+64001,rest)-sum; for(int i=1;i<ff;++i) ans2[i]='A'; if(sum[ff-1]+sum[n]-sum[f]<hpa) { ans2[ff-1]='B'; rr=hpa-(sum[n]-sum[f]); ans2[rr-sum[ff-2]]='A'; } ans1[n+1]='