[TJOI2007] 路标设置

题意

公路起点、终点和若干位置已有路标。最多新增 K 个整数位置路标，求相邻路标最大距离的最小值。

思路

假设最大距离不能超过 limit。原来长度为 gap 的一段至少需要新增：

\left\lfloor\frac{gap-1}{limit}\right\rfloor

个路标。减一是为了处理整除情况：gap=10, limit=5 时只需在中间新增一个，而不是两个。

把所有间隔的需求相加，若不超过 K，说明 limit 可行。限制越大越容易可行，因此二分第一个可行值。

Python 知识

itertools.pairwise(signs) 直接遍历相邻路标对，比手写下标更贴近“相邻间隔”的含义。
列表推导式保存所有间隔，后续二分时可以反复遍历。
sum((gap - 1) // maximum_gap for gap in gaps) 用生成器聚合新增数量。
/home/rainboy/mycode/hugo-blog/content/program_language/python/itertools_recipes.md：pairwise 的相邻元素模式。
/home/rainboy/mycode/hugo-blog/content/program_language/python/generator_expression.md：生成器与 sum。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24import sys
from itertools import pairwise


data = list(map(int, sys.stdin.buffer.read().split()))
length, n, limit = data[:3]
signs = data[3:3 + n]
gaps = [right - left for left, right in pairwise(signs)]


def possible(maximum_gap):
    needed = sum((gap - 1) // maximum_gap for gap in gaps)
    return needed <= limit


left, right = 1, max(gaps)
while left < right:
    middle = (left + right) // 2
    if possible(middle):
        right = middle
    else:
        left = middle + 1

print(left)

cpp

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58/**
 * Author by Rainboy blog: https://rainboylv.com github: https://rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

/* P3853 [TJOI2007] 路标设置 */
/* 二分最大间距的最小值，用 (gap-1)/limit 统计每段需新增路标数。 */

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

const int MAXN = 100005;

int length, n, limit;
int pos[MAXN]; // 已有路标位置
int gap[MAXN]; // 相邻路标间距

// 检查最大间距 mid 是否可行
bool check(int mid) {
    int need = 0;
    for (int i = 1; i < n; i++) {
        // 长度为 gap[i] 的线段，间距不超过 mid 需要插入的路标数
        need += (gap[i] - 1) / mid;
    }
    return need <= limit;
}

int main() {
    cin >> length >> n >> limit;
    for (int i = 1; i <= n; i++) {
        cin >> pos[i];
    }

    // 预处理相邻间距
    int max_gap = 0;
    for (int i = 2; i <= n; i++) {
        gap[i - 1] = pos[i] - pos[i - 1];
        if (gap[i - 1] > max_gap) max_gap = gap[i - 1];
    }

    // 二分答案：间距越小，需要的新路标越多
    int l = 1, r = max_gap, ans = max_gap;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid; // mid 可行，尝试更小的
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }

    cout << ans << "\n";
    return 0;
}

复杂度

每次判定扫描 $n-1$ 个间隔，时间复杂度为 $O(n\log L)$ ，保存路标和间隔需要 $O(n)$ 空间。

总结

关键不是二分本身，而是推导一个间隔需要的路标数。整除边界用 (gap-1)//limit 统一处理。

[TJOI2007] 路标设置

目录

题意

思路

Python 知识

代码

复杂度

总结