P3853 路标设置 - 二分答案详解

题目大意

给定一条长度为 L 的公路，初始有 n 个路标。可以在空地处添加最多 k 个路标，使得相邻路标之间的最大距离最小。求这个最小的最大距离。

思路分析

为什么是二分答案？

这道题的关键观察：答案具有单调性。

如果最大距离 D 可以满足，那任何 D’ > D 也一定可以满足（因为要求更松了）。反之如果 D 不满足，那 D’ < D 也一定不满足。

这种”满足/不满足”存在分界点的情况，天然适合二分。

二分什么？

二分相邻路标的最大距离 x。

  • 左边界 l = 1（最小可能的距离）
  • 右边界 r = L（最大可能的路标间距）
  • 对于每个 mid，用 check(mid) 判断是否能在插入 ≤ k 个路标的前提下使最大间距 ≤ mid

check 函数怎么写？

遍历每对相邻路标，间距为 d。如果 d > x，需要在这段之间插入路标。

关键公式： 间距为 d，要求每段 ≤ x，需要插入 ⌈d/x⌉ - 1 个路标。

用整数运算避免浮点误差：(d - 1) / x

常见错误： 用 d / x 代替 (d - 1) / x。

举例说明：d = 6，x = 2

  • 6 / 2 = 3（多算了 1 个！）
  • (6 - 1) / 2 = 5 / 2 = 2（正确）

为什么会多算？因为原始两个端点已经算路标了，不需要在末端再插一个。⌈6/2⌉ = 3 把终点也算进去了，实际只需要插入中间的 2 个。

算法流程

1
2
3
4
5
6
二分最大距离 x
  check(x):
    need = 0
    对于每段相邻路标间距 d:
      need += (d - 1) / x
    return need <= k

时间复杂度：O(n log L)

AC 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
int n, k;
int a[100005];

bool f(int x) {
    int last = 0;
    int ans = 0;
    for (int i = 0; i <= n; i++) {
        if (a[i] - last > x) {
            ans += (a[i] - last - 1) / x;
        }
        last = a[i];
    }
    return ans <= k;
}

int main() {
    int length;
    cin >> length >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);
    a[n] = length;

    int l = 1, r = length, ans = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (f(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << ans;
    return 0;
}

知识点总结

  1. 二分答案：当问题可以转化为”是否存在满足条件的解”时，对答案二分，将最优化问题转化为判定问题
  2. 单调性判断：使用二分答案的前提是答案满足单调性（可满足的区间是连续的）
  3. 向上取整技巧：⌈a/b⌉ = (a + b - 1) / b，但本题是 ⌈a/b⌉ - 1 = (a - 1) / b
  4. 贪心验证：check 函数中贪心地按最大允许间距插入路标，如果总插入数 ≤ k 则可行