【每日一题】12月16日题目精讲

题号 NC113566
名称 Superhero Battle
来源 CF1141E
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
每日一题QQ群:659028468

题解

知识点：数学
定义每n天为一个“周目”。那么本题应该是样思考：

1. 如果第一周目就可以结束，那么 模拟即可。
2. 如果第一周目无法结束，且（ 为每周目的伤害总和），那么输出-1（因为每周目后初始血量都会提升）。
3. 如果第一周目无法结束，且，那么每周目血量会减少 这么多。这时可以记录一下所有前缀和的最小值（显然是个负数），记为min。那么，当进行了 个周目后，下两个周目内一定会达到0或负数。进行模拟即可。

总复杂度：
参考代码：

#include<bits/stdc++.h>
using namespace std;
long long a[222222];
int main(){
    long long h;
    int n;
    cin>>h>>n;
    long long i,t=0;
    long long sum=0;
    long long m=0;
    for(i=0;i<n;i++){
        cin>>a[i];
        sum+=a[i];
        m=min(m,sum);
        h+=a[i];
        if(h<=0&&!t)t=i+1;
    }
    if(t){cout<<t;return 0;}
    if(sum>=0){cout<<-1;return 0;}
    else{
        t=n;
        sum*=-1;
        long long time=(h+m)/sum;
        t+=n*time;
        h-=sum*time;
    }
    while(h>0)
        for(i=0;i<n;i++){
            t++;
            h+=a[i];
            if(h<=0){cout<<t;return 0;}
        }
}

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目12月23日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴