题意:
有一个初始血量为h的怪物,有n个回合,每回合怪物的血量加di,如果怪物血量小于等于0,则怪物死亡,如果怪物不是,则n个回合循环运行,如果怪物无法死亡,则输出-1,否则输出怪物死的回合.
思路:
记录n个回合中对怪物伤害最大的一个回合,即d数组的最小前缀和,记录值mi.
如果mi+h<=0,则怪物在n回中会死亡,则暴力模拟即可。
如果mi+h>0,则看n回合对怪物造成的是否能对怪物造成伤害,如果不能,则怪物不会死,则输出-1,否则计算何时h+mi<=0,执行(h+mi)/p(p是n回合对怪物的伤害),求出执行了多少个n回,然后模拟即可.
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[200005];
int main()
{
ll h, n;
scanf("%lld%lld",&h,&n);
for(int i=1; i<=n; i++)
{
scanf("%lld",&a[i]);
}
ll mi=0, p=0, ki=0, ans=0;
for(int i=1; i<=n; i++)
{
p=p+a[i];
if(mi>p)
{
mi=p;
ki=i;
}
}
if(h+mi>0)
{
if(p>=0)
{
printf("-1\n");
}
else
{
ll bi=ceil(1.0*(h+mi)/(-p));
h=h+bi*p;
ans=ans+bi*n;
for(int i=1; i<=n; i++)
{
h=h+a[i];
ans++;
if(h<=0)
{
break;
}
}
printf("%lld\n",ans);
}
}
else
{
for(int i=1; i<=n; i++)
{
h=h+a[i];
ans++;
if(h<=0)
{
break;
}
}
printf("%lld\n",ans);
}
return 0;
}

京公网安备 11010502036488号