CF1141E Superhero Battle
A superhero fights with a monster. The battle consists of rounds, each of which lasts exactly n 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 n numbers: d1,d2,…,dn(?10^6≤di≤10^6). The i-th element means that monster's hp (hit points) changes by the value didi during the i-th minute of each round. Formally, if before the i-th minute of a round the monster's hp is h, then after the i-th minute it changes to h:=h+di
The monster's initial hp is H. It means that before the battle the monster has H hit points. Print the first minute after which the monster dies. The monster dies if its hp is less than or equal to 0. Print -1 if the battle continues infinitely.
The first line contains two integers H and n (1≤H≤10^12, 1≤n≤2?10^5). The second line contains the sequence of integers d1,d2,…,dn (?10^6≤di≤10^6), where di is the value to change monster's hp in the i-th minute of a round.
Print -1 if the superhero can't kill the monster and the battle will last infinitely. Otherwise, print the positive integer k such that k is the first minute after which the monster is dead.
1000 6 -100 -200 -300 125 77 -4
9
1000000000000 5 -1 0 0 0 0
4999999999996
10 4 -3 -6 5 4
-1
題意解釋：輸入，給定了怪物的hp和n輪戰斗對怪物造成的傷害。輸出，怪物的hp降到0及以下即被擊敗輸出第幾分鐘怪物被擊敗或-1.
解題思路：先判斷第一個周期造成的最高傷害是多少和第一個周期是否對怪物造成了傷害，來確定怪物是否能被擊敗。然后我們通過計算求出到打敗怪物的前一個周期的時間，再判斷最后一個周期何時擊敗怪物。
其實可以說是個數學題，這里我用了二分來求解，但是long long精度不夠，中間判斷的時候將long long轉為double來提高精度。
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll a[2000005]; int main() { ll hp,n; scanf("%lld%lld%lld",&hp,&n,&a[1]); ll t=a[1]; ll aa=0; ll mmin=min(t,aa); ll flag=1; for(int i=2;i<=n;++i) { scanf("%lld",&a[i]); t+=a[i]; if(mmin>t) { mmin=t; flag=i; } } ll tmp=hp; tmp+=mmin; if(tmp<=0) { for(int i=1;i<=n;++i) { hp+=a[i]; if(hp<=0) { cout<<i; return 0; } } } else { if(t>=0) { cout<<-1; return 0; } ll l=0,r=1000000000000; while(l<=r) { double mid=(l+r)/2; if(hp+(mid*t)+mmin<=0) { r=mid-1; } else { l=mid+1; } } hp+=l*t; for(int i=1;i<=n;++i) { hp+=a[i]; if(hp<=0) { cout<<i+l*n; return 0; } } } }
浙公網安備 33010602011771號