题意:
有一个初始血量为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; }