准时到达的列车最小时速 图解题解

n 趟车按顺序坐完，这题求的是哪个时速

给一个浮点数 hour 和长度 n 的整数数组 dist（dist[i] 是第 i 趟距离）。以整数时速 v 依次坐完 n 趟，第 i 趟纯行驶 dist[i]÷v 小时；列车只整点发车，前 n-1 趟到站没到整点得等下个整点才能换乘，末趟到公司就结束。求能准时（总用时 ≤hour）的最小整数时速，来不及返回 -1。题面 dist=[1,3,2]、hour=2.7 答案 3。

从时速 1 一档档往上试，慢在哪

时速最小 1、上界题目保证不超过 1e7。直接办法是从 1 起每个时速试一遍，把 n 趟用时加起来看超不超 hour，第一个不超的即答案。可最坏要试到上界，试的次数和整个值域（所有可能的时速，从 1 到某上限）一样多，是 O(C)；C 到 1e7 就试不动了。

时速和能否准时之间，卡着一条单调界线

把每个时速的总用时排一排：时速越大每趟越快，前面向上取整的项要么不变要么变小、末趟也变小，总用时只减不增——这是单调（只朝一个方向走）。于是时速切成两段，慢的都超时、快的都准时，答案是界线上第一个够快的时速，二分就能逼近它。这里二分的不是下标，是时速这个答案值本身；不直接算、猜一个值再验证行不行，叫二分答案。

判定一个时速够不够快，函数怎么写

把「行不行」做成判定函数 check(v)：遍历 dist，前 n-1 趟每趟加 ceil(dist[i]÷v)（ceil 即向上取整，对应到站没赶上整点、得等下一班），末趟加 dist[last]÷v 不取整（终点是公司、没车要赶）。累加后 ≤hour 就够快。二分取中点 mid：check 为真、mid 够快就 hi=mid，为假太慢就 lo=mid+1，缩到 lo、hi 撞上就是答案。

拿 dist=[1,3,2]、hour=2.7 逐轮验时速

把上界收到演示窗口 16 看清每步。lo=1、hi=16。第一轮 mid=8：ceil(1/8)=1、ceil(3/8)=1、末趟 2/8=0.25，合计 2.25 ≤2.7 够快，hi=8。第二轮 mid=4：1、1、2/4=0.5，合计 2.5，hi=4。第三轮 mid=2：1、ceil(3/2)=2、2/2=1，合计 4 >2.7 太慢，lo=3。第四轮 mid=3：1、1、2/3≈0.667，合计 2.667 ≤2.7，hi=3。lo=hi=3，返回 3。

本来够快的时速，怎么会被判成来不及

最容易错的是把末趟也向上取整：整点发车只约束换乘，末趟到公司就结束、没下一班要赶，把它取整会多算一段等待，能准时的时速被误判成来不及、答案偏大。其次二分的是时速值、不是数组下标；开头还得先过不可能闸——前 n-1 趟每趟至少占 1 个整点，总用时压不到 n-1 及以下，代码用 n > ceil(hour) 判死，hour=1.9 时 ceil=2、n=3 就返回 -1。

复杂度 O(n·log C)（二分 log C 轮、每轮扫 n 趟），空间 O(1)。收缩别写反：够快 hi=mid、太慢 lo=mid+1；写成 hi=mid-1 会丢答案，写成 lo=mid 只剩两档时会死循环。

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 ans

C++

#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;
    }
}