手机游戏

GitHub跳转原题关系图返回列表

二分答案。火球只向左溅射,从右往左贪心放置。将溅射伤害用代数展开后,利用滑动窗口维护三项和实现 O(1) 转移。

OJ: roj

题目 ID: 5012

难度:提高+/省选-

标签:二分答案贪心滑动窗口

创建: 2026-10-08 16:04

更新: 2026-10-08 16:04

形式化题目

给定 nn 个位置 0…n−10 \dots n-1(实际上是第一到第 nn 个怪物),第 ii 个位置有一个生命值为 mim_i 的怪物。我们可以发出至多 kk 个伤害为 pp 的火球。当一个火球打在位置 ii 时,会对该位置造成 pp 点伤害,同时会对 ii 左侧的所有位置 j≤ij \le i 造成 max⁡(0,p−(i−j)2)\max(0, p - (i-j)^2) 点溅射伤害。如果某个位置累计受到的伤害大于其生命值(即怪物的生命值变为负数),该位置的怪物即被消灭。

求最小的非负整数 pp,使得能够使用不超过 kk 个火球消灭所有的怪物。

正解

思路

这道题的最优化目标是火球的伤害 pp,并且随着 pp 的增加,消灭怪物所需的火球总数一定是非严格单调递减的,因此满足二分答案的性质。我们可以对 pp 进行二分,转化为判断:给定火球伤害 pp,能否在不超过 kk 次操作内消灭所有怪物。

在判定程序 check(p) 中,我们需要求出消灭所有怪物至少需要的火球数。由于每个火球只会对目标及其左侧造成伤害,这构成了一个明显的拓扑结构,提示我们可以采用从右向左的贪心策略。具体来说,当考虑最右侧还没被消灭的怪物所在位置 ii 时,在它右侧释放的火球不会对它产生任何伤害。为了消灭位置 ii 的怪物,我们只能在位置 ii 或更左边释放火球;而在所有能够波及位置 ii 的合法操作中,直接将火球砸在位置 ii 本身,不仅对位置 ii 造成的伤害最高(直接为 pp),而且向左产生的溅射影响范围也是最远的。因此,如果位置 ii 当前积累的伤害还不足以将其消灭,我们一定要在位置 ii 处不断放置火球,直到其被消灭为止。

设位置 jj 放了 cnt[j]cnt[j] 个火球。一个在位置 j>ij > i 释放的火球,只要 p−(j−i)2>0p - (j-i)^2 > 0,即 (j−i)2<p(j-i)^2 < p,就会对位置 ii 造成 p−(j−i)2p - (j-i)^2 的伤害。令 R=⌊p−1⌋R = \lfloor\sqrt{p-1}\rfloor,则只有满足 j−i≤Rj - i \le R 即 j∈[i+1,i+R]j \in [i+1, i+R] 范围内的右侧火球能对 ii 造成伤害。 这些火球对 ii 造成的总溅射伤害为:

∑j=i+1i+Rcnt[j]⋅(p−(j−i)2) \sum_{j=i+1}^{i+R} cnt[j] \cdot (p - (j-i)^2)
展开其中的平方项 (j−i)2=j2−2ij+i2(j-i)^2 = j^2 - 2ij + i^2,上面的和可以写成:
(p−i2)∑cnt[j]+2i∑(cnt[j]⋅j)−∑(cnt[j]⋅j2) (p - i^2) \sum cnt[j] + 2i \sum (cnt[j] \cdot j) - \sum (cnt[j] \cdot j^2)
因此,我们可以通过维护窗口 [i+1,i+R][i+1, i+R] 内的三个前缀和或滑动窗口和:cnt[j]cnt[j]、cnt[j]⋅jcnt[j] \cdot j 以及 cnt[j]⋅j2cnt[j] \cdot j^2,来在 O(1)O(1) 的时间内计算出右侧已释放的火球对位置 ii 造成的总溅射伤害。如果这个伤害不够,就在位置 ii 补足,并相应地更新滑动窗口的数据结构。

对于二分的上界,由于只需要保证最大的怪物的血量减到负数,我们可以把所有的火球全砸在最右侧的位置 n−1n-1,为了保证最左侧的怪物受到伤害也大于 max⁡(m)+1\max(m) + 1,我们可以设 p=max⁡(m)+1+(n−1)2p = \max(m) + 1 + (n-1)^2。

细节坑点: 滑动窗口时需要注意边界条件 R=0R = 0(即 p=1p = 1),此时火球毫无溅射作用,只能造成单点伤害。此时窗口应当恒定为空。如果直接将判断逻辑写死把“加入元素”操作也屏蔽掉,那么在考虑下一个点时就相当于自身没获得伤害,就会把本该正确的 p=1p=1 误判。正确做法是如果 R≥1R \ge 1,才执行完整的弹窗、加窗维护流程。

代码

python
#!/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()
cpp
/**
 * 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;
}

复杂度

  • 时间复杂度:计算二分上界为 O(N)O(N)。二分的范围大约为 U≈max⁡(m)+N2≈109+2.5×109≈3.5×109U \approx \max(m) + N^2 \approx 10^9 + 2.5 \times 10^9 \approx 3.5 \times 10^9,二分的次数约为 log⁡2U≈32\log_2 U \approx 32 次。每次 check 过程从右向左扫描 NN 个位置,状态维护和更新皆为 O(1)O(1),总时间开销为 O(N)O(N)。因此总体时间复杂度为 O(Nlog⁡(max⁡(m)+N2))O(N \log (\max(m) + N^2))。
  • 空间复杂度:由于仅维护长度为 NN 的数组记录火球放置次数和初始血量等数据,O(N)O(N)。

总结

  • 二分答案的单调性:本题中目标求能完成任务的“最小” pp,而显然火球威力 pp 越大,消灭所有怪物所需的总火球数越少或者不变。这个明显的单调性提示我们把“最优化”转化为“判定”问题(二分答案)。
  • 通过方向限制与贪心简化状态:因为火球只能向左侧发生溅射伤害,从右向左处理使得当前考虑的怪物不受左侧后续决策的干扰。每次遇到剩余血量不足的怪物,在它本身位置放置火球既能造成最大的自身伤害,又能对剩余还未处理的左侧怪物造成最大且最远的溅射伤害,是严格无后效性的最优选择。
  • 代数展开分离变量:计算右侧火球产生的溅射伤害公式是 p−(i−j)2p - (i-j)^2。如果暴力累加,复杂度不可接受。我们将它展开为 (p−i2)+2ij−j2(p-i^2) + 2ij - j^2,发现其中只包含与 jj 相关的三项:11、jj、j2j^2。于是滑动窗口只需要维护这三个独立的部分之和,就能 O(1)O(1) 算出原式的值。
  • 溅射半径与边界特判:本题最大的陷阱在于溅射半径 R=⌊p−1⌋R = \lfloor\sqrt{p-1}\rfloor 的计算,这定义了某个位置 ii 受到右侧哪些火球的影响,即受影响区间为 [i−R,i][i-R, i](从右向左看则是 [i+1,i+R][i+1, i+R] 对 ii 产生影响)。当 p=1p = 1 时,R=0R = 0,表示完全没有左向的溅射。如果没处理好 R=0R=0 的滑动窗口逻辑,可能会导致无法加入自身放的火球,使得算法错误地认为即使放了火球也不能消灭它,从而误判 p=1p=1。
  • “消灭”定义引发的边界:题面指出“血量为负的时候它就死了”,因此造成的总伤害 SS 必须严格大于生命值 mim_i,即 S≥mi+1S \ge m_i + 1。这也是在推算补足伤害和判定死活时必须小心处理的地方。