首先,回合数越少越好。我们发现,让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; }