1870. 准时到达的列车最小时速

Problem: 1870. 准时到达的列车最小时速

思路

题目中，速度越大越能在要求的时间内到达，而我们要求最小时间，很自然地就联想到二分答案。

但是有一些小细节需要注意，例如，答案的右边界是max(dist)，因为hour是最大小数位为二位的小数，因此最小可能需要的时间是需要除以0.01的。

复杂度

• 时间复杂度: $O(nlogU)$，U为max(dist)
• 空间复杂度: $O(1)$

Code

class Solution {
    public int minSpeedOnTime(int[] dist, double hour) {
        int n = dist.length;
        if (hour <= n - 1) return -1;
        int max = 0;
        for (int i = 0; i < n; i++) {
            if (dist[i] > max) max = dist[i];
        }
        int l = 1;
        int r = max * 100;
        while (l <= r) {
            int m = (l + r) >> 1;
            double now = cal(m, dist, hour);
            if (now < hour) {
                r = m - 1;
            } else if (now > hour) {
                l = m + 1;
            } else {
                return m;
            }
        }
        return l;
    }

    double cal(int speed, int [] dist, double hour) {
        double now = 0;
        int n = dist.length;
        for (int i = 0; i < n - 1; i++) {
            now += Math.ceil(dist[i] / (double) speed);
        }
        now += dist[n - 1] / (double) speed;
        return now;
    }
}