Valhalla Siege 题解
题目传送门
一道二分题。
先观察数据范围，\(1\le n,q\le 200,000\)，显然需要 \(O(n\log n)\) 的复杂度。且 \(1\le k_i\le 10^{14}\)，需要开 long long。
我们需要二分到第一个血量大于伤害值的武士的位置，前面的武士都死了。而在 C++ 算法库中，有一个函数 upper_bound（底层原理是二分）正好可以帮助我们实现此功能。
另外，为了优化时间复杂度，我们选择用前缀和来存储武士们的血量与伤害。
Code
#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
ll n, q, d; // d 表示伤害
ll sum[200005]; // 前缀和
signed main() {
ios :: sync_with_stdio(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
ll x;
cin >> x;
sum[i] = sum[i - 1] + x;
}
for (int i = 1; i <= q; i++) {
ll x;
cin >> x;
d += x;
ll loc = upper_bound(sum + 1, sum + n + 1, d) - sum; // 查找第一个血量大于伤害的武士的位置
loc--; // 死了多少个武士
if (loc >= n) { // 全死了的情况
d = 0; // 伤害清零
cout << n << "\n"; // 全部复活，所以有 n 个武士
}
else cout << n - loc << "\n"; // 剩余的武士
}
}