题解 | #魔法信标网络#

题目链接

题目描述

在一个哨兵塔网络中，每座塔 $i$ 有 $a_i$ 个信标，每个信标能覆盖距离 $r$ 以内的所有塔。一座塔的“屏障强度”是所有能覆盖到它的信标总数。现在有 $k$ 个额外的信标可以自由分配。任务是找到一种分配方案，使得所有塔中最低的屏障强度被最大化。

解题思路

这是一个典型的“最大化最小值”问题，是二分答案的经典应用场景。我们可以二分搜索最终可以达到的最低屏障强度 $X$ ，然后设计一个 check 函数来验证，在最多使用 $k$ 个额外信标的前提下，是否能让所有塔的屏障强度都达到 $X$ 。

`check(X)` 函数设计

check 函数的目标是判断：是否存在一种分配方案，使得所有塔的强度 $\ge X$ 。我们可以使用贪心策略来判断：

计算初始强度：首先，我们需要知道在不增加任何信标的情况下，每座塔的屏障强度。这可以通过一次滑动窗口（或前缀和）在 $\mathcal{O}(n)$ 时间内完成。设塔 $i$ 的初始强度为 $s_i$ 。
贪心增援：我们从左到右（ $i=0, 1, \dots, n-1$ ）检查每座塔。对于塔 $i$ ，我们计算它当前的屏障强度，该强度由两部分构成：初始强度 $s_i$ 和我们在此前决策中已经增加的、且能覆盖到塔 $i$ 的信标所带来的强度。
如果塔 $i$ 的当前总强度小于 $X$ ，说明它未达到目标，我们必须增援信标。为了让增援的信标能够最大化地对后续的塔（ $i+1, i+2, \dots$ ）产生帮助，最贪心的策略是将所有需要的信标都放置在能覆盖塔 $i$ 的最右边的塔上，即塔 $i+r$ （若 $i+r \ge n$ ，则放在塔 $n-1$ ）。
状态维护：在遍历过程中，我们需要一个数组 added_beacons 来记录在每座塔上增援的信标数量，并用一个滑动窗口来高效计算这些增援信标对当前塔 $i$ 的贡献。同时，用一个变量 total_added 累计增援的信标总数。
判断：如果在任何一步，total_added 超过了 $k$ ，则说明目标 $X$ 太高，无法实现，check 函数返回 false。如果遍历完所有塔都没有超过 $k$ ，则返回 true。

二分搜索

下界： $0$
上界：一个足够大的数，例如所有初始信标总和加上 $k$ 。 $3 \cdot 10^{14}$ 是一个安全的上界。

通过二分搜索框架，我们不断调用 check(X) 函数来缩小可行解的范围，最终找到答案。整个算法的时间复杂度为 $\mathcal{O}(n \log V)$ ，其中 $V$ 是强度的上界。所有强度和信标数量都需要使用 long long 类型存储。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;
using ll = long long;

int r, n;
ll k;
vector<ll> a;

bool check(ll target_strength) {
    vector<ll> s(n);
    ll current_window_sum = 0;

    // 计算初始强度
    for (int i = 0; i < n; ++i) {
        if (i == 0) {
            for (int j = 0; j <= r && j < n; ++j) current_window_sum += a[j];
        } else {
            if (i - r - 1 >= 0) current_window_sum -= a[i - r - 1];
            if (i + r < n) current_window_sum += a[i + r];
        }
        s[i] = current_window_sum;
    }

    vector<ll> added_beacons(n + r + 1, 0); // 额外空间防止越界
    ll total_added = 0;
    ll current_added_contribution = 0;

    for (int i = 0; i < n; ++i) {
        if (i == 0) {
            for (int j = 0; j <= r && j < n; ++j) current_added_contribution += added_beacons[j];
        } else {
            if (i - r - 1 >= 0) current_added_contribution -= added_beacons[i - r - 1];
            if (i + r < n) current_added_contribution += added_beacons[i + r];
        }

        if (s[i] + current_added_contribution < target_strength) {
            ll needed = target_strength - (s[i] + current_added_contribution);
            total_added += needed;
            if (total_added > k) return false;

            int pos = min(n - 1, i + r);
            added_beacons[pos] += needed;
            current_added_contribution += needed;
        }
    }
    return true;
}

int main() {
    cin >> r >> k >> n;
    a.resize(n);
    ll total_sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        total_sum += a[i];
    }

    ll left = 0, right = total_sum + k + 1, ans = 0;

    while (left < right) {
        // mid偏左，配合 left = mid + 1, right = mid
        ll mid = left + (right - left) / 2;
        if (check(mid)) {
            // mid可行，尝试更大的值，搜索区间变为 [mid + 1, right)
            left = mid + 1;
        } else {
            // mid不可行，答案在左侧，搜索区间变为 [left, mid)
            right = mid;
        }
    }

    // left是第一个不满足条件的值，所以答案是 left - 1
    cout << left - 1 << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    static int r, n;
    static long k;
    static long[] a;

    static boolean check(long targetStrength) {
        long[] s = new long[n];
        long currentWindowSum = 0;

        // 计算初始强度
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                for (int j = 0; j <= r && j < n; j++) currentWindowSum += a[j];
            } else {
                if (i - r - 1 >= 0) currentWindowSum -= a[i - r - 1];
                if (i + r < n) currentWindowSum += a[i + r];
            }
            s[i] = currentWindowSum;
        }

        long[] addedBeacons = new long[n + r + 1];
        long totalAdded = 0;
        long currentAddedContribution = 0;

        for (int i = 0; i < n; i++) {
            if (i == 0) {
                for (int j = 0; j <= r && j < n; j++) currentAddedContribution += addedBeacons[j];
            } else {
                if (i - r - 1 >= 0) currentAddedContribution -= addedBeacons[i - r - 1];
                if (i + r < n) currentAddedContribution += addedBeacons[i + r];
            }

            if (s[i] + currentAddedContribution < targetStrength) {
                long needed = targetStrength - (s[i] + currentAddedContribution);
                totalAdded += needed;
                if (totalAdded > k) return false;

                int pos = Math.min(n - 1, i + r);
                addedBeacons[pos] += needed;
                currentAddedContribution += needed;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        r = sc.nextInt();
        k = sc.nextLong();
        n = sc.nextInt();
        a = new long[n];
        long totalSum = 0;
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
            totalSum += a[i];
        }

        long left = 0, right = totalSum + k + 1;

        while (left < right) {
            // mid偏左，配合 left = mid + 1, right = mid
            long mid = left + (right - left) / 2;
            if (check(mid)) {
                // mid可行，尝试更大的值，搜索区间变为 [mid + 1, right)
                left = mid + 1;
            } else {
                // mid不可行，答案在左侧，搜索区间变为 [left, mid)
                right = mid;
            }
        }
        
        // left是第一个不满足条件的值，所以答案是 left - 1
        System.out.println(left - 1);
    }
}

import sys

def check(target_strength, r, k, n, a):
    s = [0] * n
    current_window_sum = 0
    
    # 计算初始强度
    for i in range(n):
        if i == 0:
            for j in range(min(n, r + 1)):
                current_window_sum += a[j]
        else:
            if i - r - 1 >= 0:
                current_window_sum -= a[i - r - 1]
            if i + r < n:
                current_window_sum += a[i + r]
        s[i] = current_window_sum

    added_beacons = [0] * (n + r + 1)
    total_added = 0
    current_added_contribution = 0
    
    for i in range(n):
        if i == 0:
            for j in range(min(n, r + 1)):
                current_added_contribution += added_beacons[j]
        else:
            if i - r - 1 >= 0:
                current_added_contribution -= added_beacons[i - r - 1]
            if i + r < n:
                current_added_contribution += added_beacons[i + r]

        if s[i] + current_added_contribution < target_strength:
            needed = target_strength - (s[i] + current_added_contribution)
            total_added += needed
            if total_added > k:
                return False
            
            pos = min(n - 1, i + r)
            added_beacons[pos] += needed
            current_added_contribution += needed
            
    return True

# 主逻辑
r = int(sys.stdin.readline())
k = int(sys.stdin.readline())
n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))

total_sum = sum(a)
left, right = 0, total_sum + k + 1

while left < right:
    # mid偏左，配合 left = mid + 1, right = mid
    mid = left + (right - left) // 2
    if mid == 0: # 0 总是可行的
        left = mid + 1
        continue
    if check(mid, r, k, n, a):
        # mid可行，尝试更大的值，搜索区间变为 [mid + 1, right)
        left = mid + 1
    else:
        # mid不可行，答案在左侧，搜索区间变为 [left, mid)
        right = mid

# left是第一个不满足条件的值，所以答案是 left - 1
print(left - 1)

算法及复杂度

算法：二分答案 + 贪心 + 滑动窗口
时间复杂度： $\mathcal{O}(n \log V)$ ，其中 $n$ 是哨兵塔的数量， $V$ 是屏障强度的最大可能值（上界）。check 函数内部的两次滑动窗口遍历都是 $\mathcal{O}(n)$ 的。
空间复杂度： $\mathcal{O}(n)$ ，主要用于存储初始强度数组和增援的信标数组。