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[];
int main()
{
ll hp,n;
scanf("%lld%lld%lld",&hp,&n,&a[]);
ll t=a[];
ll aa=;
ll mmin=min(t,aa);
ll flag=;
for(int i=;i<=n;++i)
{
scanf("%lld",&a[i]);
t+=a[i];
if(mmin>t)
{
mmin=t;
flag=i;
}
}
ll tmp=hp;
tmp+=mmin;
if(tmp<=)
{
for(int i=;i<=n;++i)
{
hp+=a[i];
if(hp<=)
{
cout<<i;
return ;
}
}
}
else
{
if(t>=)
{
cout<<-;
return ;
}
ll l=,r=;
while(l<=r)
{
double mid=(l+r)/;
if(hp+(mid*t)+mmin<=)
{
r=mid-;
}
else
{
l=mid+;
}
}
hp+=l*t;
for(int i=;i<=n;++i)
{
hp+=a[i];
if(hp<=)
{
cout<<i+l*n;
return ;
}
}
}
}
最新文章
- div高度根据内容自动增大
- Photoshop制作的海报修改~
- Java 对象,数组 与 JSON 字符串 相互转化
- js 监听输入框输入事件兼容ie7
- 业务中Spring使用
- 理解中WebAPI的属性和相关操作 FormBody和 FormUri等(WebAPI 二)
- bzoj 5016: [Snoi2017]一个简单的询问
- [ZJOI 2010]count 数字计数
- sessionStorage的保存和获取
- 初学html的单词笔记
- day 56 jQuery学习
- ML平台_小米深度学习平台的架构与实践
- Python2.7-array
- HP 打印机监控
- 【BZOJ4236】JOIOJI STL
- Spring Data JPA 关系映射(一对一,一对多,多对多 )
- MVC Ajax Helpers
- 机器学习之感知器算法原理和Python实现
- Shiro——认证概述
- Java Collection.RP