Codeforces1141E(E题）Superhero Battle

冷不防 2021-10-15 04:25 237阅读 0赞

A superhero fights with a monster. The battle consists of rounds, each of which lasts exactly  nn minutes. After a round ends, the next round starts immediately. This is repeated over and over again.

Each round has the same scenario. It is described by a sequence of nn numbers: d1,d2,…,dnd1,d2,…,dn (−106≤di≤106−106≤di≤106). The ii-th element means that monster's hp (hit points) changes by the value didi during the ii-th minute of each round. Formally, if before the ii-th minute of a round the monster's hp is hh, then after the ii-th minute it changes to h:=h\+dih:=h+di.

The monster's initial hp is HH. It means that before the battle the monster has HH hit points. Print the first minute after which the monster dies. The monster dies if its hp is less than or equal to 00. Print \-1 if the battle continues infinitely.

Input

The first line contains two integers HH and nn (1≤H≤10121≤H≤1012, 1≤n≤2⋅1051≤n≤2⋅105). The second line contains the sequence of integers d1,d2,…,dnd1,d2,…,dn (−106≤di≤106−106≤di≤106), where didi is the value to change monster's hp in the ii-th minute of a round.

Output

Print \-1 if the superhero can't kill the monster and the battle will last infinitely. Otherwise, print the positive integer kk such that kk is the first minute after which the monster is dead.

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 const int N=200000+10;
     5 const ll INF = 0x3f3f3f3f3f3f3f3f;
     6 int t,n,m,k,q;
     7 unsigned long long ans;
     8 ll cnt,flag,temp,sum;
     9 ll h;
    10 int a[N];
    11 int main()
    12 {
    13     cin>>h>>n;
    14     ll H=h;
    15     ll minl=INF;
    16     for(int i=1;i<=n;i++){
    17         cin>>a[i];
    18         sum+=a[i];
    19         minl=min(minl,sum);
    20         if(h+sum<=0){
         //如果h加上第一轮的sum小于0，就输出sum值所在下标 
    21             cout<<i<<endl;
    22             return 0;
    23         }
    24     }
    25     if(minl>=0||sum>=0){
         // 和最小序列为正数或一轮所有值的和为正数，输出-1，代表不能实现将hp扣为0及一下 
    26         cout<<-1<<endl;
    27         return 0;
    28     }
    29     cnt=(H+minl)/-sum;//hp加上和最小序列后除-sum得整数轮数，为n-2 或n-1 ,取决于数是到 和最小序列最后一个，还是之前就使hp<=0 
    30     if((H+minl)%-sum)//正好最大负值+整数个sum使hp=0 
    31         cnt++;                 //为n-1 或n 
    32     ans=(unsigned long long)cnt*n;//轮数乘以每轮个数 
    33     h=H+sum*cnt;
    34     if(h<=0){            //和最小序列和sum相等，即正好整数个sum使h<=0 
    35         cout<<ans<<endl;
    36         return 0;
    37     }
    38     for(int i=1;i<=n;i++){
         //累加最后一轮 
    39         h+=a[i];
    40         if(h<=0){
    41             cout<<ans+i<<endl;
    42             return 0;
    43         }
    44     }
    45 }

题意分析：输入一个整数H，代表血量，每一轮的攻击消耗血量或增加血量，求消耗完时是第多少次攻击。

转载于:https://www.cnblogs.com/yuanhang110/p/11234451.html