题解思路

对于长度为 n 的城市数组 cities，每座城市初始拥有若干 CDN 机房。每个机房的服务半径为 r，相当于它能为相距不超过 r 的城市提供服务。给定还可以新建 k 个机房，允许在同一城市重复建设，目标是使所有城市的最小“服务质量”（即能访问到的机房总数）最大化。

我们可以抽象为：让每个城市 i “窗口”内（[i–r, i+r]）的机房总和至少达到 m，问是否能用不超过 k 次增量操作做到这一点。增量操作：在某个城市 j 新增一台机房，会使得所有覆盖到 j 的城市窗口内总和加 1。

• 二分答案：对最小服务质量 m 进行二分搜索。
• 可行性检验：固定候选值 m，判断是否在 k 次新增内使所有城市窗口和 ≥ m。
• 贪心策略：从城市 0 到 n–1 遍历，维护当前对每个城市由新增机房带来的累计增量 cur_add（通过差分数组模拟区间加法）。若某城市窗口和 initial[i] + cur_add 小于 m，则在最右能覆盖该城市的点 j = min(n–1, i+r) 上新增所需的机房数 need = m – (initial[i] + cur_add)，并将 need 加到差分数组上。若累计新增量超出 k，则判定不可行。

这样，每次检验的时间复杂度为 O(n)，二分需要 O(log T) 次，其中 T 约为初始最小窗口和 + k。

算法流程

1. 前缀和
   计算城市机房数的前缀和 ps，用以快速求任意区间和。

2. 初始窗口和
   对每座城市 i，计算其初始服务质量

   initial[i] = sum(cities[max(0, i-r) .. min(n-1, i+r)]) 
              = ps[min(n-1,i+r)] - ps[max(0,i-r)-1]
   

3. 二分答案

   • lo = 0, hi = min(initial) + k
   • 循环直至 lo < hi：设 mid = (lo + hi + 1) // 2
     • 若 check(mid) 可行，则 lo = mid
     • 否则 hi = mid - 1

4. 可行性检验 check(m)

   • 设差分数组 diff[n] 全 0，cur_add = 0，used = 0
   • 对 i 从 0 遍历到 n-1：
     1. cur_add += diff[i]
     2. 计算当前覆盖：cover = initial[i] + cur_add
     3. 若 cover < m，需新增 need = m - cover：
        • used += need，若 used > k 返回 false
        • 选点 j = min(n-1, i+r)，其增量区间 [L = max(0,j-r), R = min(n-1,j+r)]，而此时 L=i，故：

          cur_add += need
          if R+1 < n: diff[R+1] -= need
          

   • 若遍历结束仍未超出 k，则返回 true。

5. 返回 最终二分出的 lo。

复杂度分析

• 计算初始前缀和和窗口和：O(n)
• 每次可行性检验：O(n)
• 二分次数：O(log(初始最小窗口和 + k))，该值上限约 O(log(n·max(cities)+k))
• 总复杂度：O(n log (n·max(cities)+k))，对 n ≤ 10^5 完全可行。

代码实现

Python 实现

def max_min_service(cities, r, k):
    n = len(cities)
    # 1. 前缀和
    ps = [0] * n
    ps[0] = cities[0]
    for i in range(1, n):
        ps[i] = ps[i-1] + cities[i]
    # 2. 初始窗口和
    initial = [0] * n
    for i in range(n):
        L = max(0, i - r)
        R = min(n - 1, i + r)
        initial[i] = ps[R] - (ps[L - 1] if L > 0 else 0)
    # 二分上下界
    lo, hi = 0, min(initial) + k

    def check(m):
        diff = [0] * (n + 1)  # 差分数组，多一位便于操作
        cur_add = used = 0
        for i in range(n):
            cur_add += diff[i]
            cover = initial[i] + cur_add
            if cover < m:
                need = m - cover
                used += need
                if used > k:
                    return False
                # 在 j 位置新增 need 台机房
                j = min(n - 1, i + r)
                R = min(n - 1, j + r)
                # 新增在 i 开始生效，到 R 结束
                cur_add += need
                diff[R + 1] -= need
        return True

    # 二分寻找最大可行 m
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if check(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

# 读入输出
if __name__ == "__main__":
    import sys
    data = sys.stdin.read().split()
    r, k, n = map(int, data[:3])
    cities = list(map(int, data[3:]))
    print(max_min_service(cities, r, k))

Java 实现

import java.io.*;
import java.util.*;

public class Main {
    public static long maxMinService(int[] cities, int r, long k) {
        int n = cities.length;
        // 1. 前缀和
        long[] ps = new long[n];
        ps[0] = cities[0];
        for (int i = 1; i < n; i++) {
            ps[i] = ps[i-1] + cities[i];
        }
        // 2. 初始窗口和
        long[] initial = new long[n];
        for (int i = 0; i < n; i++) {
            int L = Math.max(0, i - r);
            int R = Math.min(n - 1, i + r);
            initial[i] = ps[R] - (L > 0 ? ps[L-1] : 0);
        }
        long lo = 0, hi = Arrays.stream(initial).min().getAsLong() + k;

        // 检验函数
        class Checker {
            boolean check(long m) {
                long[] diff = new long[n + 1];
                long curAdd = 0, used = 0;
                for (int i = 0; i < n; i++) {
                    curAdd += diff[i];
                    long cover = initial[i] + curAdd;
                    if (cover < m) {
                        long need = m - cover;
                        used += need;
                        if (used > k) return false;
                        int j = Math.min(n - 1, i + r);
                        int R = Math.min(n - 1, j + r);
                        curAdd += need;
                        diff[R + 1] -= need;
                    }
                }
                return true;
            }
        }

        Checker checker = new Checker();
        while (lo < hi) {
            long mid = (lo + hi + 1) >>> 1;
            if (checker.check(mid)) lo = mid;
            else hi = mid - 1;
        }
        return lo;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int r = Integer.parseInt(br.readLine());
        long k = Long.parseLong(br.readLine());
        int n = Integer.parseInt(br.readLine());
        String[] parts = br.readLine().split(" ");
        int[] cities = new int[n];
        for (int i = 0; i < n; i++) cities[i] = Integer.parseInt(parts[i]);
        System.out.println(maxMinService(cities, r, k));
    }
}

C++ 实现

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

ll maxMinService(const vector<int>& cities, int r, ll k) {
    int n = cities.size();
    // 1. 前缀和
    vector<ll> ps(n);
    ps[0] = cities[0];
    for (int i = 1; i < n; i++) {
        ps[i] = ps[i-1] + cities[i];
    }
    // 2. 初始窗口和
    vector<ll> initial(n);
    for (int i = 0; i < n; i++) {
        int L = max(0, i - r);
        int R = min(n - 1, i + r);
        initial[i] = ps[R] - (L > 0 ? ps[L-1] : 0);
    }
    ll lo = 0, hi = *min_element(initial.begin(), initial.end()) + k;

    // 检验函数
    auto check = [&](ll m) {
        vector<ll> diff(n+1, 0);
        ll curAdd = 0, used = 0;
        for (int i = 0; i < n; i++) {
            curAdd += diff[i];
            ll cover = initial[i] + curAdd;
            if (cover < m) {
                ll need = m - cover;
                used += need;
                if (used > k) return false;
                int j = min(n - 1, i + r);
                int R = min(n - 1, j + r);
                curAdd += need;
                diff[R+1] -= need;
            }
        }
        return true;
    };

    // 二分
    while (lo < hi) {
        ll mid = (lo + hi + 1) >> 1;
        if (check(mid)) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

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

    int r; ll k; int n;
    cin >> r >> k >> n;
    vector<int> cities(n);
    for (int i = 0; i < n; i++) {
        cin >> cities[i];
    }
    cout << maxMinService(cities, r, k) << "\n";
    return 0;
}

题目内容

$CDN$(content delivery network，内容分发网络)机房可以加速网站内容的加载速度，通过在地理位置上靠近用户的地点存储网站的内容副本。

给定一个下标从 $0$ 开始长度为 $n$ 的整数数组 $cities$ ，其中 $cities$ 表示第 $i$ 座 城市中现有的 $CDN$ 机房数量。

每个 $CDN$ 机房能够服务的城市覆盖范围由其所在位置决定，所有节点具有相同的城市盖范围。

如果给定的覆盖范围是 $r$ ，则位于城市 $i$ 的 $CDN$ 机房可以为其周围 $∣i-j∣<=r$ 范围内的所有城市提供服务，这里 $∣x∣$ 表示 $x$ 的绝对值。例如，$∣5-3∣=2，∣4-9∣=5$ 。

一座城市的“服务质量”定义为能够访问到的 $CDN$ 机房的数量，你的任务是在全国范围内选择多个城市来新建 $k$ 个 $CDN$ 机房(同一个城市可重复建设)，以确保即使在网络流量高峰时期也能提供最佳的服务质量。

现在给定两个整数 $r$ 和 $k$ ，你需要决定在哪些城市新建 $k$ 个 $CDN$ 机房，使所有城市中最小的服务质量达到最大，并返回最小服务质量。

输入描述

第一行数字为 $r$ ，第二行数字为 $k$ ，第三行数字为城市数量 $n$ ，第四行 $n$ 个数字为 $cities$ 的值

输入限制：

$1<=n<=100000$

$0<=cities[i]<=100000$

$0<=r<=n-1$

$0<=k<=10^9$

输出描述

返回所有城市中最小服务质量达到最大时的 $CDN$ 节点数

样例1

输入

1
2
5
1 2 4 9 3

输出

5

说明

输入转换成 $cities=[1,2,4,9,3]，r=1，k=2$

最优方案之一是把 $2$ 个节点都建在城市 $1$ ，建设完后每座城市的CDN节点数目分别为 $[1,4,4,9,3]$ 。

• 城市 $0$ 的节点数目为 $1+4=5$。

• 城市 $1$ 的节点数目为 $1+4+4=9$ 。

• 城市 $2$ 的节点数目为 $4+4+9=17$ 。

• 城市 $3$ 的节点数目为 $4+9+3=16$ 。

• 城市 $4$ 的节点数目为 $9+3=12$ 。

这些城市中节点数最小的是 $5$ ，已无法使得这个最小值更大。

样例2

输入

0
3
4
5 5 5 5

输出

5

说明

输入转换成 $cities=[5,5,5,5]，r=0，k=3$。无论如何安排，总有一座城市的 $CDN$ 节点数目是 $5$ ，所以最优解是 $5$ 。