【每日一题】12月16日 Superhero Battle C++ 题解

首先,回合数越少越好。我们发现,让boss剩下最多(但是在一个回合内能够击杀)的血量时回合数最少

把boss的血量状态压缩，然后进行枚举，代码如下：

#include <bits/stdc++.h>
#define R register
#define ll long long
#define cmin(a, b) ((a < b) ? a : b)
#define cmax(a, b) ((a < b) ? b : a)
const int MaxN = 2e5 + 10;
typedef std::pair<int, int> pa;
ll h, n;
ll d[MaxN], sum[MaxN];
int main()
{
    scanf("%lld%lld", &h, &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &d[i]), sum[i] = sum[i - 1] + d[i];
    for (int i = 1; i <= n; i++)
        if (h + sum[i] <= 0)
            return 0 * printf("%d\n", i);
    if (sum[n] >= 0)
        return 0 * printf("-1");
    ll min = *std::min_element(sum + 1, sum + n + 1);
    ll cnt = (h + min - 1) / (-sum[n]) + 1;
    h += cnt * sum[n];
    for (int i = 1; i <= n; i++)
        if (h + sum[i] <= 0)
            return 0 * printf("%lld\n", i + cnt * n);
    return 0;
}