准时到达的列车最小时速 图解题解
这道题到底在问什么
- 输入
- dist=[1,3,2], hour=6
- 输出
- 1
- 输入
- dist=[1,3,2], hour=2.7
- 输出
- 3
- 输入
- dist=[1,3,2], hour=1.9
- 输出
- -1
最优解：一步一步想明白
- 3记牢:时速越大用时越短,可行性单调,于是二分时速 v。检查一个 v:前 n-1 趟用时 ceil(dist[i]/v)、最后一趟不取整,求和 ≤ hour 则可行、收紧右界,否则抬高左界。先过不可能闸 n 大于 ceil(hour) 返回 -1。二分的是时速值,不是下标。
- 4先看清画面。上面这排格子是三趟列车的距离 1、3、2,你要按这个顺序依次坐完,总时间只有 2.7 小时。右边面板记三件事:时速的候选范围、当前正在检验的时速 v、以及这个 v 下的累计用时,现在都还没开始。思路不是硬凑时速,而是二分猜一个时速 v,再验证它够不够快。
- 5开二分前先过一道快速闸。前 n-1 趟每趟至少要占 1 个整点,加上最后一趟,哪怕时速无穷大,总用时也压不到 n-1 小时以下。所以只要趟数 n 大于 ceil(hour),就说明再快也排不进这点时间,直接返回 -1。这里 n 是 3,ceil(2.7) 是 3,3 并不大于 3,闸通过,可以放心去二分找答案。
- 6框定答案的范围。时速最小是 1,再慢就不是正整数了。上界方面,参考代码直接用题目保证的 1e7,这里为了让每一步都看得清,把演示窗口缩到 16,机制完全一样。接下来不逐个试,而是二分:取范围中点当候选时速 v,验证这个 v 够不够准时。请记住,右边面板里动的是时速 v 的范围,数组这排列车始终不动。
- 7开始第一轮二分。当前范围是 1 到 16,取中点得候选时速 v 等于 8。也就是先问:以时速 8 开,总用时能不超过 2.7 小时吗?下面逐趟算它的用时,把它们累加起来,再和 2.7 比。
- 8看第 0 趟,距离 1。纯行驶时间是 1 除以 8 等于 0.125 小时,但它不是最后一趟,到站后要等到下一个整点才能换乘,所以用时向上取整成 1 小时。累计用时来到 1。
- 9看第 1 趟,距离 3。纯行驶时间是 3 除以 8 等于 0.375 小时,但它不是最后一趟,到站后要等到下一个整点才能换乘,所以用时向上取整成 1 小时。累计用时来到 2。
- 10看最后一趟,距离 2。它是终点,到了就到了,不用再等下一个整点,所以用时不向上取整,直接 2 除以 8 等于 0.25。把它加进累计用时,现在合计 2.25 小时,这就是时速 8 下的总用时。
- 11三趟车算完,总用时 2.25 小时,不超过 2.7,说明时速 8 能准时到达。既然 8 就够了,那更快的时速就不用看了,把右界收到 8,范围变成 1 到 8。注意 8 本身可能就是最小答案,所以右界取 8 而不是 8 减 1,继续往更慢里试。
- 12第二轮二分。上一轮把范围收到了 [1, 8],取中点得候选时速 v 等于 4。同样地问一句:时速 4 够快能准时吗?逐趟算用时、累加、再和 2.7 比。
- 13看第 0 趟,距离 1。纯行驶时间是 1 除以 4 等于 0.25 小时,但它不是最后一趟,到站后要等到下一个整点才能换乘,所以用时向上取整成 1 小时。累计用时来到 1。
- 14看第 1 趟,距离 3。纯行驶时间是 3 除以 4 等于 0.75 小时,但它不是最后一趟,到站后要等到下一个整点才能换乘,所以用时向上取整成 1 小时。累计用时来到 2。
- 15看最后一趟,距离 2。它是终点,到了就到了,不用再等下一个整点,所以用时不向上取整,直接 2 除以 4 等于 0.5。把它加进累计用时,现在合计 2.5 小时,这就是时速 4 下的总用时。
- 16三趟车算完,总用时 2.5 小时,不超过 2.7,说明时速 4 能准时到达。既然 4 就够了,那更快的时速就不用看了,把右界收到 4,范围变成 1 到 4。注意 4 本身可能就是最小答案,所以右界取 4 而不是 4 减 1,继续往更慢里试。
- 17第三轮二分。上一轮把范围收到了 [1, 4],取中点得候选时速 v 等于 2。同样地问一句:时速 2 够快能准时吗?逐趟算用时、累加、再和 2.7 比。
- 18看第 0 趟,距离 1。纯行驶时间是 1 除以 2 等于 0.5 小时,但它不是最后一趟,到站后要等到下一个整点才能换乘,所以用时向上取整成 1 小时。累计用时来到 1。
- 19看第 1 趟,距离 3。纯行驶时间是 3 除以 2 等于 1.5 小时,但它不是最后一趟,到站后要等到下一个整点才能换乘,所以用时向上取整成 2 小时。累计用时来到 3。
- 20看最后一趟,距离 2。它是终点,到了就到了,不用再等下一个整点,所以用时不向上取整,直接 2 除以 2 等于 1。把它加进累计用时,现在合计 4 小时,这就是时速 2 下的总用时。
- 21三趟车算完,总用时 4 小时,超过了 2.7,说明时速 2 太慢、赶不上。那 2 以及更慢的都不行,把左界抬到 3,范围变成 3 到 4,接着往更快里找。
- 22第四轮二分。上一轮把范围收到了 [3, 4],取中点得候选时速 v 等于 3。同样地问一句:时速 3 够快能准时吗?逐趟算用时、累加、再和 2.7 比。
- 23看第 0 趟,距离 1。纯行驶时间是 1 除以 3 等于 0.333 小时,但它不是最后一趟,到站后要等到下一个整点才能换乘,所以用时向上取整成 1 小时。累计用时来到 1。
- 24看第 1 趟,距离 3。纯行驶时间是 3 除以 3 等于 1 小时,但它不是最后一趟,到站后要等到下一个整点才能换乘,所以用时向上取整成 1 小时。累计用时来到 2。
- 25看最后一趟,距离 2。它是终点,到了就到了,不用再等下一个整点,所以用时不向上取整,直接 2 除以 3 等于 0.667。把它加进累计用时,现在合计 2.667 小时,这就是时速 3 下的总用时。
- 26三趟车算完,总用时 2.667 小时,不超过 2.7,说明时速 3 能准时到达。既然 3 就够了,那更快的时速就不用看了,把右界收到 3,范围变成 3 到 3,此时左界和右界已经相等,二分结束,答案候选锁定为 3。
- 27二分收束了。左界和右界都停在 3,说明 3 是能准时到达的最小时速:它可行,而比它慢的 2 已经验证过来不及。回看时速 3 那一轮,前两趟各取整成 1 小时,最后一趟 2 除以 3 约等于 0.667 小时不取整,合计约 2.667 小时,刚好卡在 2.7 以内。
- 28收个尾。整道题的巧劲在于把「最小时速是多少」这个难题,翻译成「时速 v 够不够准时」这个好答的判断题,再靠单调性二分时速。dist = 1,3,2、hour = 2.7,我们只检验了 8、4、2、3 这几个候选时速,就锁定最小时速是 3。可行性检查里那句「前面取整、末趟不取整」,正是整点发车规则的精确翻译,千万别把最后一趟也取整了。
⚠️ 容易写错的地方
✗ 错：把最后一趟也向上取整
✓ 对：只有前 n-1 趟因为要等整点发车才取整,最后一趟到站即结束、用时不取整,直接 dist[last]/v
这是本题最容易错的一点,也是它和普通二分答案的区别所在。整点发车规则只约束「换乘」,最后一趟没有下一班要赶,把它也取整会把总用时算大,导致本来能准时的时速被误判成来不及,答案偏大
✗ 错：把二分用在数组下标上,以为是在 dist 里找位置
✓ 对：二分的是「时速 v 这个答案值」,范围是 1 到上界,不是数组下标
这是二分答案的核心转弯。答案的取值有单调可行性,才把二分从「找元素」升级成「找答案分界点」。误当成下标二分会完全跑偏,数组也不需要排序
✗ 错：忘了不可能闸,或用错判断把整数溢出
✓ 对：开头先判 dist.length 大于 ceil(hour) 直接返回 -1;累加用时在 C++/Java 里用 double,别用 int
前 n-1 趟每趟至少占 1 个整点,总用时压不到 n-1 以下,趟数比 ceil(hour) 还多就绝无可能,不加这道闸二分会在无解时给出错误的上界值。累加若用整型还会丢掉小数、把最后一趟的零头抹掉
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
def minSpeedOnTime(self, dist: List[int], hour: float) -> int:
def check(v: int) -> bool:
s = 0
for i, d in enumerate(dist):
t = d / v
s += t if i == len(dist) - 1 else ceil(t)
return s <= hour
if len(dist) > ceil(hour):
return -1
r = 10**7 + 1
ans = bisect_left(range(1, r), True, key=check) + 1
return -1 if ans == r else ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int minSpeedOnTime(vector<int>& dist, double hour) {
if (dist.size() > ceil(hour)) {
return -1;
}
const int m = 1e7;
int l = 1, r = m + 1;
int n = dist.size();
auto check = [&](int v) {
double s = 0;
for (int i = 0; i < n; ++i) {
double t = dist[i] * 1.0 / v;
s += i == n - 1 ? t : ceil(t);
}
return s <= hour;
};
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l > m ? -1 : l;
}
};Java
import java.util.*;
class Solution {
public int minSpeedOnTime(int[] dist, double hour) {
if (dist.length > Math.ceil(hour)) {
return -1;
}
final int m = (int) 1e7;
int l = 1, r = m + 1;
while (l < r) {
int mid = (l + r) >> 1;
if (check(dist, mid, hour)) {
r = mid;
} else {
l = mid + 1;
}
}
return l > m ? -1 : l;
}
private boolean check(int[] dist, int v, double hour) {
double s = 0;
int n = dist.length;
for (int i = 0; i < n; ++i) {
double t = dist[i] * 1.0 / v;
s += i == n - 1 ? t : Math.ceil(t);
}
return s <= hour;
}
}复杂度
时间
O(n log C)
n 是列车趟数,C 是时速上界(参考代码取 1e7)。二分在时速范围上进行,最多 log C 轮;每一轮做一次可行性检查,要扫一遍全部 n 趟车累加用时,是 O(n)。两者相乘就是 O(n log C)。演示里 n 等于 3,只检验了 4 个候选时速就收敛
空间
O(1)
按峰值算。除了输入数组,只用了 l、r、mid 和一个累加用时的变量,都是常数个标量,不随规模增长。Python 里的 range 是惰性对象、不真的展开成数组,bisect 也只用常数额外空间。全程没有开新数组,所以额外空间是常数 O(1)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 准时到达的列车最小时速 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么时速可以拿来二分?单调性到底体现在哪?+
关键是「给定时速 v 能不能准时」这个判断关于 v 是单调的。时速定得越大,每趟车行驶越快,前面取整的项要么不变要么变小,最后一趟也变小,总用时只减不增;时速越小则越慢、总用时越大。于是存在一条分界时速,快于等于它就准时、慢于它就迟到,不会来回横跳。有了这个单调性,就能像在有序序列里找边界一样二分时速,每次用可行性检查决定往快收还是往慢收,把线性枚举压成对数级。
为什么偏偏最后一趟不向上取整?+
向上取整的物理含义是「等下一个整点发车」。前 n-1 趟到站后如果不是整点,必须干等到下一个整点才能上下一班车,这段等待时间体现在向上取整上。而最后一趟的终点是公司,到了就到了,后面没有要赶的车,自然不用等、也就不取整,直接用纯行驶时间 dist[last] 除以 v。把最后一趟也取整,等于凭空多算了一段不存在的等待,会让总用时偏大、答案偏保守。
和普通的「在有序数组里二分找目标」比,这题难在哪?+
普通二分的判定是「当前值和目标比大小」,一眼就能写;二分答案的难点在于要自己设计判定函数,把「这个时速能不能准时」翻译成一段可计算的检查。这题的判定就是那句可行性检查:前面取整、末趟不取整,累加后和 hour 比。想清楚判定单调、范围取 1 到上界、可行时右界取 mid、以及开头那道不可能闸这几点,剩下的二分骨架就和普通二分一模一样了。这类题的通用套路是,先问「能不能达到目标」比直接求最优值好答得多。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 准时到达的列车最小时速 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。