【Codeforces Round #547 (Div. 3) E. Superhero Battle】思维题

E. Superhero Battle

题意

有一个怪兽，初始血量为$H$,他的血量变化情况是一个长度为$n$轮的周期。问怪兽会在第几轮死去。

$1\le H\le 10^{12}$
$1\le n\le 2\times 10^5$
做法

首先如果怪兽血量在一个周期内不曾小于等于$0$而且每个周期之后怪兽血量增加，直接输出$?1$。
之后要知道，怪兽在某个完整的周期之前到达x血量，怪兽就撑不过这轮。
这个$x$的求法就是遍历一遍周期，找到某个时刻怪兽血量消耗最多。
之后就假设怪兽初始血量为$H?x$。看怪兽能撑过几个完整的轮，设这里轮数为$k$，每轮怪兽血量减少$sum$,则要满足
$$sum\times k+x\ge H$$
$$k\ge \frac{H?x}{sum}$$
所以不等式右面要上取整得到$k$，之后再$O(n)$的进行一个周期看怪兽在第几轮死即可。
代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
int a[maxn];
int n;
ll H;
ll sum;
int check(ll mid)
{
    ll tt=H;tt+=(mid-1)*sum;if(tt<=0) return 0;for(int i=1;i<=n;i++){
    tt+=a[i];if(tt<=0) return i;}return -1;
}
int main()
{
    scanf("%lld%d",&H,&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);sum=0;int flag=0;ll tmp=H;ll minn=LL_INF;int pos;for(int i=1;i<=n;i++){
    sum+=a[i];tmp+=a[i];if(sum<minn){
    minn=sum;pos=i;}if(tmp<=0){
    flag=i;break;}}if(flag!=0){
    printf("%d\n",flag);return 0;}if(sum>=0){
    printf("-1");return 0;}minn=-minn;sum=-sum;ll ans=(H-minn)/sum+((H-minn)%sum!=0);H=H-ans*sum;if(H==0){
    printf("%lld\n",ans*n);return 0;}for(int i=1;i<=n;i++){
    H+=a[i];if(H<=0){
    printf("%lld\n",ans*n+i);return 0;}}return 0;
}