【每日一题】Superhero Battle 题解

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;
}