[TJOI2007] 路标设置
二分允许的最大间距，用 (gap-1)//limit 统计每段必须新增的路标数。
OJ: luogu
题目 ID: P3853
难度:普及/提高-
标签:二分答案贪心python
日期: 2026-07-16 17:49
题意
公路起点、终点和若干位置已有路标。最多新增 K 个整数位置路标，求相邻路标最大距离的最小值。
思路
假设最大距离不能超过 limit。原来长度为 gap 的一段至少需要新增：
个路标。减一是为了处理整除情况：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
import 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
/**
* 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-08-14 19:14
*/
/* P3853 [TJOI2007] 路标设置 */
/* 二分答案：找最小的最大间距，使需要新增的路标数 <= limit。 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int length, n, limit; // 道路长度、已有路标数、最多可新增数
int pos[MAXN]; // 已有路标位置
int gap[MAXN]; // 相邻路标间距
// 最大间距 mid 是否可行：需要新增的路标数不超过 limit。
// check 单调：false false ... false true true ... true。
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;
}
// 在 [l, r] 中查找第一个满足 check(pos) 的位置。
// 要求 check 单调：false false ... false true true ... true。
// 调用时要保证 r 是一个真实或虚拟的可行位置。
int first_true(int l, int r) {
while (l < r) {
int mid = l + (r - l) / 2;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
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];
}
// max_gap 一定可行（不需要新增路标），作为虚拟可行位置
cout << first_true(1, max_gap) << '\n';
return 0;
}复杂度
每次判定扫描
总结
关键不是二分本身，而是推导一个间隔需要的路标数。整除边界用 (gap-1)//limit 统一处理。