二分最大速度，给定速度后顺着维护每个地点可行签收时间区间的下界，线性判断是否能按时送完。
OJ: luogu
题目 ID: P1542
难度:普及+/提高
标签:二分贪心数学模拟
日期: 2026-06-20 13:31
题意
有 n 个地点需要按顺序依次送达。
第 i 个地点给出：
- 可签收时间区间
[x_i, y_i] - 从前一个地点到这里的距离
s_i
小 K 可以在某个地点提前到达并等待， 但不能晚于该地点的签收上界。
要求最小化整条路线允许使用的最大速度。
思路
先看一个可以直接验证想法的朴素解：
cpp
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
int n;
double l[MAXN], r[MAXN], s[MAXN];
bool check(double speed) {
double low = l[1];
double high = r[1];
for (int i = 2; i <= n; i++) {
double need = s[i] / speed;
low = max(l[i], low + need);
high = r[i];
if (low > high) return false;
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> l[i] >> r[i] >> s[i];
}
// 小数据暴力版仍然直接二分答案。
// 这题核心是可行性判定，不存在更自然的离散暴力。
double left = 0.0;
double right = 1e8;
for (int i = 0; i < 100; i++) {
double mid = (left + right) / 2.0;
if (check(mid)) right = mid;
else left = mid;
}
cout << fixed << setprecision(2) << right << '\n';
return 0;
}这题答案有很明显的单调性：
- 如果某个速度可行，更大的速度也一定可行；
- 如果某个速度不可行，更小的速度也一定不可行。
所以整体框架是二分答案。
关键在于如何判断给定速度 v 是否可行。
设当前已经处理到第 i 个地点，
并且在这个地点能够合法完成签收的时间范围是 [low, high]。
到下一个地点至少要花：
s_{i+1} / v
所以最早只能在：
low + s_{i+1} / v
时到达第 i+1 个地点。
如果这个时刻早于 x_{i+1}，可以等到 x_{i+1}；
如果它晚于 y_{i+1}，就说明这个速度不够快。
因此新的最早可行时间是：
max(x_{i+1}, low + s_{i+1}/v)
只要这个值不超过 y_{i+1}，就还能继续。
于是 check(v) 只需要从前往后线性扫描一遍地点，
不断更新这个“当前最早可行签收时间”即可。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000 + 5;
int n;
double l[MAXN], r[MAXN], s[MAXN];
// 判断最大速度 speed 是否可行。
bool check(double speed) {
double low = l[1];
double high = r[1];
for (int i = 2; i <= n; i++) {
double need = s[i] / speed;
// 从上一站可行到达区间 [low, high] 出发，
// 加上这一段行驶时间 need 后，到达当前站的可行时间区间是：
// [low + need, +inf)
//
// 由于上一站可以等待到任意不超过 high 的时刻再出发，
// 所以只要当前站签收区间与 [low + need, +inf) 有交集即可。
low = max(l[i], low + need);
high = r[i];
if (low > high) return false;
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> l[i] >> r[i] >> s[i];
}
double left = 0.0;
double right = 1e8;
for (int i = 0; i < 100; i++) {
double mid = (left + right) / 2.0;
if (check(mid)) {
right = mid;
} else {
left = mid;
}
}
cout << fixed << setprecision(2) << right << '\n';
return 0;
}复杂度
每次判定
总结
这题本质上不是路径规划，而是“速度够不够快”的可行性判定。
一旦把固定速度后的问题转成时间区间递推， 整题就是标准的“二分答案 + 线性 check”。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
