魔法信标网络

题意

$n$ 座哨兵塔排成一排，第 $i$ 座塔有 $\text{beacons}[i]$ 个信标。塔 $i$ 的每个信标能覆盖所有满足 $|i - j| \le \text{radius}$ 的塔 $j$ 。塔 $j$ 的"屏障强度"定义为所有能覆盖它的信标总数，即：

$ $\text{strength}[j] = \sum_{i=\max(0,\,j-r)}^{\min(n-1,\,j+r)} \text{beacons}[i]$ $

现在可以额外部署 $k$ 个信标到任意塔中，问：所有塔中最低屏障强度的最大值是多少？

思路

看到"最小值最大"这种措辞，你应该立刻想到什么？——二分答案。

为什么能二分？

如果最低屏障强度能达到 $x$ ，那么 $x - 1$ 肯定也能达到（少放几个信标就行）。这个单调性就是二分的基础。

二分之后怎么 check？

假设我们二分的目标是"所有塔的屏障强度都 $\ge \text{target}$ "，怎么判断需要几个新信标？

先用前缀和 $O(n)$ 算出每座塔的初始屏障强度。然后从左到右扫描：

如果塔 $j$ 的当前强度已经 $\ge \text{target}$ ，跳过。
如果塔 $j$ 还差 $\text{need}$ 才能达标，我们需要在某座塔上放 $\text{need}$ 个信标来补。放在哪里最优？

关键观察：放在 $\min(j + \text{radius}, n-1)$ 最好。为什么？因为这个位置刚好还能覆盖到塔 $j$ （距离恰好 $\le \text{radius}$ ），而且向右延伸得最远，尽可能多地惠及后面的塔。

放完之后，这些新信标对后续塔的影响怎么维护？用差分数组。新增的 $\text{need}$ 个信标放在位置 $p$ ，它们覆盖 $[p - \text{radius}, p + \text{radius}]$ ，但我们是从左到右扫的，所以只需记录它在右边什么时候"过期"：在位置 $\min(p + \text{radius}, n-1) + 1$ 处减去 $\text{need}$ 。

每一轮 check 是 $O(n)$ 的。二分的范围？下界是初始最小强度，上界可以取所有信标之和加 $k$ （极端情况下 $\text{radius} \ge n$ 时每个信标覆盖全部塔）。二分轮数 $O(\log(\text{sum} + k))$ 。

总时间复杂度 $O(n \log V)$ ，其中 $V$ 是答案的值域上界。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int radius, k, n;
    cin >> radius >> k >> n;
    vector<long long> beacons(n);
    for(int i = 0; i < n; i++) cin >> beacons[i];

    vector<long long> prefix(n+1, 0);
    for(int i = 0; i < n; i++) prefix[i+1] = prefix[i] + beacons[i];

    vector<long long> strength(n);
    for(int j = 0; j < n; j++){
        int lo = max(0, j - radius);
        int hi = min(n-1, j + radius);
        strength[j] = prefix[hi+1] - prefix[lo];
    }

    auto check = [&](long long target) -> bool {
        long long used = 0;
        vector<long long> diff(n+1, 0);
        long long extra = 0;
        for(int j = 0; j < n; j++){
            extra += diff[j];
            long long cur = strength[j] + extra;
            if(cur < target){
                long long need = target - cur;
                used += need;
                if(used > k) return false;
                int p = min(j + radius, n - 1);
                extra += need;
                int end = min(p + radius, n - 1);
                if(end + 1 <= n) diff[end + 1] -= need;
            }
        }
        return true;
    };

    long long lo = *min_element(strength.begin(), strength.end());
    long long hi = prefix[n] + k;
    while(lo < hi){
        long long mid = lo + (hi - lo + 1) / 2;
        if(check(mid)) lo = mid;
        else hi = mid - 1;
    }
    cout << lo << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int radius = sc.nextInt();
        long k = sc.nextLong();
        int n = sc.nextInt();
        long[] beacons = new long[n];
        for (int i = 0; i < n; i++) beacons[i] = sc.nextLong();

        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + beacons[i];

        long[] strength = new long[n];
        for (int j = 0; j < n; j++) {
            int lo = Math.max(0, j - radius);
            int hi = Math.min(n - 1, j + radius);
            strength[j] = prefix[hi + 1] - prefix[lo];
        }

        long left = Long.MAX_VALUE;
        for (long s : strength) left = Math.min(left, s);
        long right = prefix[n] + k;

        while (left < right) {
            long mid = left + (right - left + 1) / 2;
            if (check(strength, mid, k, radius, n)) left = mid;
            else right = mid - 1;
        }
        System.out.println(left);
    }

    static boolean check(long[] strength, long target, long k, int radius, int n) {
        long used = 0;
        long[] diff = new long[n + 1];
        long extra = 0;
        for (int j = 0; j < n; j++) {
            extra += diff[j];
            long cur = strength[j] + extra;
            if (cur < target) {
                long need = target - cur;
                used += need;
                if (used > k) return false;
                int p = Math.min(j + radius, n - 1);
                extra += need;
                int end = Math.min(p + radius, n - 1);
                if (end + 1 <= n) diff[end + 1] -= need;
            }
        }
        return true;
    }
}

import sys
input = sys.stdin.readline

def solve():
    radius = int(input())
    k = int(input())
    n = int(input())
    beacons = list(map(int, input().split()))

    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + beacons[i]

    strength = [0] * n
    for j in range(n):
        lo = max(0, j - radius)
        hi = min(n - 1, j + radius)
        strength[j] = prefix[hi + 1] - prefix[lo]

    def check(target):
        used = 0
        diff = [0] * (n + 1)
        extra = 0
        for j in range(n):
            extra += diff[j]
            cur = strength[j] + extra
            if cur < target:
                need = target - cur
                used += need
                if used > k:
                    return False
                p = min(j + radius, n - 1)
                extra += need
                end = min(p + radius, n - 1)
                if end + 1 <= n:
                    diff[end + 1] -= need
        return True

    left = min(strength)
    right = prefix[n] + k
    while left < right:
        mid = left + (right - left + 1) // 2
        if check(mid):
            left = mid
        else:
            right = mid - 1
    print(left)

solve()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const radius = parseInt(lines[0]);
    const k = parseInt(lines[1]);
    const n = parseInt(lines[2]);
    const beacons = lines[3].split(' ').map(Number);

    const prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + beacons[i];

    const strength = new Array(n);
    for (let j = 0; j < n; j++) {
        const lo = Math.max(0, j - radius);
        const hi = Math.min(n - 1, j + radius);
        strength[j] = prefix[hi + 1] - prefix[lo];
    }

    function check(target) {
        let used = 0;
        const diff = new Array(n + 1).fill(0);
        let extra = 0;
        for (let j = 0; j < n; j++) {
            extra += diff[j];
            const cur = strength[j] + extra;
            if (cur < target) {
                const need = target - cur;
                used += need;
                if (used > k) return false;
                const p = Math.min(j + radius, n - 1);
                extra += need;
                const end = Math.min(p + radius, n - 1);
                if (end + 1 <= n) diff[end + 1] -= need;
            }
        }
        return true;
    }

    let left = Math.min(...strength);
    let right = prefix[n] + k;
    while (left < right) {
        const mid = left + Math.ceil((right - left) / 2);
        if (check(mid)) left = mid;
        else right = mid - 1;
    }
    console.log(left);
});

复杂度

时间复杂度： $O(n \log V)$ ，其中 $V$ 是二分的值域上界， $V = \sum \text{beacons}[i] + k$ 。
空间复杂度： $O(n)$ 。