二分答案。火球只向左溅射,从右往左贪心放置。将溅射伤害用代数展开后,利用滑动窗口维护三项和实现 O(1) 转移。
OJ: roj
题目 ID: 5012
难度:提高+/省选-
标签:二分答案贪心滑动窗口
创建: 2026-10-08 16:04
更新: 2026-10-08 16:04
形式化题目
给定
求最小的非负整数
正解
思路
这道题的最优化目标是火球的伤害
在判定程序 check(p) 中,我们需要求出消灭所有怪物至少需要的火球数。由于每个火球只会对目标及其左侧造成伤害,这构成了一个明显的拓扑结构,提示我们可以采用从右向左的贪心策略。具体来说,当考虑最右侧还没被消灭的怪物所在位置
设位置
对于二分的上界,由于只需要保证最大的怪物的血量减到负数,我们可以把所有的火球全砸在最右侧的位置
细节坑点: 滑动窗口时需要注意边界条件
代码
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 15:09
# update_at: 2026-10-08 15:09
import sys
from math import isqrt
def used_fireballs(hp: list[int], p: int, k: int) -> int:
"""伤害为 p 时清场所需的最少火球数,超过 k 立即返回 k+1(只关心是否可行)。
火球只伤及自身与左侧,故从右往左贪心:位置 i 只受距离 j-i <= R 的右侧火球
溅射,窗口 [i+1, i+R] 的三项和即可 O(1) 求出已受溅射
(p - i*i)*sum_cnt + 2*i*sum_j - sum_j2;不足 m_i+1 就在 i 上补 ceil(缺/p) 个。
"""
n = len(hp)
r = isqrt(p - 1) # 溅射伤害严格大于 0 的最远距离,p = 1 时为 0
cnt = [0] * n
sum_cnt = sum_j = sum_j2 = total = 0
for i in range(n - 1, -1, -1):
splash = (p - i * i) * sum_cnt + 2 * i * sum_j - sum_j2
need = hp[i] + 1 - splash # 血量变负才算死,累计伤害要到 hp[i] + 1
c = (need + p - 1) // p if need > 0 else 0
total += c
if total > k:
return k + 1
cnt[i] = c
# r == 0(即 p == 1)时溅射半径为 0,左侧怪物吃不到任何伤害,窗口恒为空:
# 既不弹出也不加入,否则 p = 1 会被误判成不可行。
if r:
# 窗口由 [i+1, i+r] 移到下一位置的 [i, i-1+r]:先弹掉距离恰为 r+1 的 i+r
creep = i + r
if creep < n:
cr = cnt[creep]
sum_cnt -= cr
sum_j -= cr * creep
sum_j2 -= cr * creep * creep
sum_cnt += c # 再加入位置 i 的火球来源
sum_j += c * i
sum_j2 += c * i * i
return total
def min_damage(hp: list[int], k: int) -> int:
"""二分最小的火球伤害 p,使清场所需火球数不超过 k。"""
# 上界:只往最右怪物砸 1 个火球,p = max(hp)+1+(n-1)^2 时最左怪物的溅射
# 也达到 p-(n-1)^2 = max(hp)+1,足以击杀它,故该上界必然可行。
lo, hi = 1, max(hp) + 1 + (len(hp) - 1) ** 2
while lo < hi:
mid = (lo + hi) // 2
if used_fireballs(hp, mid, k) <= k:
hi = mid
else:
lo = mid + 1
return lo
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, k = next(data), next(data)
hp = [next(data) for _ in range(n)]
print(min_damage(hp, k))
if __name__ == "__main__":
solve()/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-08 15:08
* update_at: 2026-10-08 15:08
*/
// 一本通 1676《手机游戏》/ roj 5012:二分答案 + 从右向左贪心 + 滑动窗口三项和
//
// 题意:n 个怪物排成一行,第 i 个血量为 m_i。射出 k 个伤害均为 p 的火球,
// 火球打在位置 i 时对该位置造成 p 点伤害,并对左侧第 j 个怪物(j <= i)
// 造成 max(0, p - (i-j)^2) 点溅射伤害。血液变负即死亡(即累计伤害 >= m_i + 1),
// 求能消灭全部怪物的最小 p。
//
// 做法:p 越大越容易成功,故对答案二分,check(p) 求清场所需的最少火球数:
// 火球只向左溅射,从右往左处理。轮位置 i 时,右侧已放置的火球对 i 的溅射伤害
// 记为 S;若 S < m_i + 1,缺少的伤害只能在 i 或更左补,而砸在 i 自身
// (伤害最高、向左溅射也最远)严格不劣,故在 i 处补 ceil((m_i+1-S)/p) 个火球。
// S 用滑动窗口 + 三项和 O(1) 维护:设 cnt[j] 为位置 j 的火球数,
// R = floor(sqrt(p-1)) 是溅射严格大于 0 的最远距离,则 j 落在 [i+1, i+R] 时
// S = sum cnt[j]*(p - (j-i)^2)
// = (p - i^2)*sumCnt + 2*i*sumJ - sumJ2
// 其中 sumCnt/sumJ/sumJ2 是窗口内 cnt[j]、cnt[j]*j、cnt[j]*j*j 的和。
// 总复杂度 O(n log(max(m) + n^2))。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 50000 + 5;
ll n; // 怪物个数
ll k; // 火球数量上限
ll m[MAXN]; // m[i]:第 i 个怪物的血量(0 下标)
ll cnt[MAXN]; // cnt[i]:check 中贪心决定砸在位置 i 的火球数
// 整数开方:返回 floor(sqrt(x)),x >= 0。sqrtl 只做初值估计,再用循环夹逼到精确值。
ll isqrt(ll x) {
if (x <= 0) return 0;
long double approx = sqrtl((long double)x);
ll r = approx; // 浮点估计可能有 1 的误差,下面两个循环修正
while ((r + 1) * (r + 1) <= x) r++;
while (r * r > x) r--;
return r;
}
// 判断伤害 p 能否用不超过 k 个火球消灭所有怪物。
// 返回 false 时只保证"所需火球数 > k",不需要给出具体数量。
bool check(ll p) {
ll R = isqrt(p - 1); // 溅射伤害 > 0 的最远距离;p = 1 时 R = 0
ll sumCnt = 0; // 窗口内 cnt[j] 之和
ll sumJ = 0; // 窗口内 cnt[j] * j 之和
ll sumJ2 = 0; // 窗口内 cnt[j] * j * j 之和
ll total = 0; // 已用火球总数
for (ll i = n - 1; i >= 0; i--) {
// 当前窗口是右侧距离 <= R 的火球来源,即 [i+1, i+R]
ll splash = (p - i * i) * sumCnt + 2 * i * sumJ - sumJ2;
ll need = m[i] + 1 - splash; // 还差多少伤害(血量必须 < 0)
ll c = 0;
if (need > 0) {
c = (need + p - 1) / p; // ceil(need / p)
total += c;
if (total > k) return false;
}
cnt[i] = c;
// R == 0 时溅射半径为 0(p = 1),左侧怪物吃不到任何伤害,窗口恒为空:
// 此时既不能弹出也不能加入,否则 p = 1 会被误判成不可行。
if (R >= 1) {
// 窗口从 [i+1, i+R] 移到下一位置的 [i, i-1+R]:先去掉距离恰为 R+1 的 i+R
ll creep = i + R;
if (creep < n) {
sumCnt -= cnt[creep];
sumJ -= cnt[creep] * creep;
sumJ2 -= cnt[creep] * creep * creep;
}
// 再加入位置 i 的火球来源
sumCnt += c;
sumJ += c * i;
sumJ2 += c * i * i;
}
}
return total <= k;
}
void read_input() {
if (!(cin >> n >> k)) return;
for (ll i = 0; i < n; i++) {
cin >> m[i];
}
}
void solve() {
ll top = 0; // 最大血量,用来定二分上界
for (ll i = 0; i < n; i++) {
if (m[i] > top) top = m[i];
}
// 上界:只在最右位置放 1 个火球,p = top+1+(n-1)^2 时它到最左怪物的溅射
// 也有 p-(n-1)^2 = top+1 >= m_i+1,故 check(hi) 必为真。
ll lo = 1;
ll hi = top + 1 + (n - 1) * (n - 1);
while (lo < hi) {
ll mid = lo + (hi - lo) / 2;
if (check(mid)) {
hi = mid;
} else {
lo = mid + 1;
}
}
cout << lo << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
solve();
return 0;
}复杂度
- 时间复杂度:计算二分上界为
。二分的范围大约为 ,二分的次数约为 次。每次 check过程从右向左扫描个位置,状态维护和更新皆为 ,总时间开销为 。因此总体时间复杂度为 。 - 空间复杂度:由于仅维护长度为
的数组记录火球放置次数和初始血量等数据, 。
总结
- 二分答案的单调性:本题中目标求能完成任务的“最小”
,而显然火球威力 越大,消灭所有怪物所需的总火球数越少或者不变。这个明显的单调性提示我们把“最优化”转化为“判定”问题(二分答案)。 - 通过方向限制与贪心简化状态:因为火球只能向左侧发生溅射伤害,从右向左处理使得当前考虑的怪物不受左侧后续决策的干扰。每次遇到剩余血量不足的怪物,在它本身位置放置火球既能造成最大的自身伤害,又能对剩余还未处理的左侧怪物造成最大且最远的溅射伤害,是严格无后效性的最优选择。
- 代数展开分离变量:计算右侧火球产生的溅射伤害公式是
。如果暴力累加,复杂度不可接受。我们将它展开为 ,发现其中只包含与 相关的三项: 、 、 。于是滑动窗口只需要维护这三个独立的部分之和,就能 算出原式的值。 - 溅射半径与边界特判:本题最大的陷阱在于溅射半径
的计算,这定义了某个位置 受到右侧哪些火球的影响,即受影响区间为 (从右向左看则是 对 产生影响)。当 时, ,表示完全没有左向的溅射。如果没处理好 的滑动窗口逻辑,可能会导致无法加入自身放的火球,使得算法错误地认为即使放了火球也不能消灭它,从而误判 。 - “消灭”定义引发的边界:题面指出“血量为负的时候它就死了”,因此造成的总伤害
必须严格大于生命值 ,即 。这也是在推算补足伤害和判定死活时必须小心处理的地方。