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"; // 剩余的武士
	}
}