【每日一题】Superhero Battle 题解

Superhero Battle

https://ac.nowcoder.com/acm/problem/113566

Description

n个数字一个循环,每秒经过一个数字,血量变化为 总血量为HP,问HP经过多少秒后小于等于0
Codeforces Difficulty 1700

Solution

分类讨论

  • 找最大的一个前缀和,如果这个最大的前缀和 大于HP,那么可以在一轮内完成。
  • 再看一轮的前缀和 ,如果小于等于0,则经过多少轮血量都只会增加不会减少。
  • 如果 先扣出来 , 随后剩余的看要经过多少轮才能结束(轮数要向上取整),最后走一轮统计即可。

时间复杂度

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
typedef long long ll;
ll a[N], sum[N];
int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
  ll H; int n; cin >> H >> n;
  ll maxz = -1e18;  
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
    a[i] = -a[i];
    sum[i] = sum[i - 1] + a[i];
    maxz = max(maxz, sum[i]);
  }
  if(maxz >= H) {
    for(int i = 1; i <= n; i++) {
      H -= a[i];
      if(H <= 0) {
        cout << i << '\n';
        return 0;
      }
    }
  }
  if(sum[n] <= 0) {
    cout << -1 << '\n';
  } else {
    ll now = H - maxz, ans = 0;
    ll cnt = (now + sum[n] - 1) / sum[n];
    now -= cnt * sum[n];
    now += maxz, ans += n * cnt;
    for(int i = 1; i <= n; i++) {
      now -= a[i]; ans++;
      if(now <= 0) {
        break;
      }
    }
    cout << ans << '\n';
  }
  return 0;
}
Kurisu与牛客的每日一题 文章被收录于专栏

每日一题

全部评论

相关推荐

犹豫的小狐狸刷了100道题:你是我在牛课上见到的最漂亮的女孩了
点赞 评论 收藏
分享
叶扰云倾:进度更新,现在阿里云面完3面了,感觉3面答得还行,基本都答上了,自己熟悉的地方也说的比较细致,但感觉面试官有点心不在焉不知道是不是不想要我了,求阿里收留,我直接秒到岗当阿里孝子,学校那边的房子都退租了,下学期都不回学校,全职猛猛实习半年。这种条件还不诱人吗难道 然后现在约到了字节的一面和淘天的复活赛,外加猿辅导。华为笔试完没动静。 美团那边之前投了个base广州的,把我流程卡麻了,应该是不怎么招人,我直接简历挂了,现在进了一个正常的后端流程,还在筛选,不知道还有没有hc。
点赞 评论 收藏
分享
评论
4
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务