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

leetcode

字数统计: 830阅读时长: 3 min

 2021/05/23   Share

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

给你一个浮点数 hour ，表示你到达办公室可用的总通勤时间。要到达办公室，你必须按给定次序乘坐 n 趟列车。另给你一个长度为 n 的整数数组 dist ，其中 dist[i] 表示第 i 趟列车的行驶距离（单位是千米）。

每趟列车均只能在整点发车，所以你可能需要在两趟列车之间等待一段时间。

例如，第 1 趟列车需要 1.5 小时，那你必须再等待 0.5 小时，搭乘在第 2 小时发车的第 2 趟列车。
返回能满足你准时到达办公室所要求全部列车的最小正整数时速（单位：千米每小时），如果无法准时到达，则返回 -1 。

生成的测试用例保证答案不超过 107 ，且 hour 的小数点后最多存在两位数字。

示例 1：

输入：dist = [1,3,2], hour = 6
输出：1
解释：速度为 1 时：

- 第 1 趟列车运行需要 1/1 = 1 小时。
- 由于是在整数时间到达，可以立即换乘在第 1 小时发车的列车。第 2 趟列车运行需要 3/1 = 3 小时。
- 由于是在整数时间到达，可以立即换乘在第 4 小时发车的列车。第 3 趟列车运行需要 2/1 = 2 小时。

你将会恰好在第 6 小时到达。

示例 2：

输入：dist = [1,3,2], hour = 2.7
输出：3
解释：速度为 3 时：

- 第 1 趟列车运行需要 1/3 = 0.33333 小时。
- 由于不是在整数时间到达，故需要等待至第 1 小时才能搭乘列车。第 2 趟列车运行需要 3/3 = 1 小时。
- 由于是在整数时间到达，可以立即换乘在第 2 小时发车的列车。第 3 趟列车运行需要 2/3 = 0.66667 小时。
- 你将会在第 2.66667 小时到达。

示例 3：

1
2
3

输入：dist = [1,3,2], hour = 1.9
输出：-1
解释：不可能准时到达，因为第 3 趟列车最早是在第 2 小时发车。

提示：

n == dist.length
1 <= n <= 105
1 <= dist[i] <= 105
1 <= hour <= 109
hours 中，小数点后最多存在两位数字

C++程序：

函数：

class Solution {
public:
    bool check(vector<int>& dist, double& hour, int index) {
        double time = 0;
        for (int i = 0; i < dist.size() - 1; i++) {
            time += ceil((double)dist[i] / index);
        }
        time += (double)dist.back() / index;

        return time <= hour;
    }
    int minSpeedOnTime(vector<int>& dist, double hour) {
        if (dist.size() > ceil(hour)) {
            return -1;
        }

        int left = 1;
        int right = INT_MAX;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (check(dist, hour, mid)) {
                right = mid;
            }
            else {
                left = mid + 1;
            }
        }

        return left;
    }
};

lambda：

//简单，好写，但时间稍微慢了点？奇怪了
class Solution {
public:
    int minSpeedOnTime(vector<int>& dist, double hour) {
        if (dist.size() > ceil(hour)) {
            return -1;
        }

        int left = 1;
        int right = INT_MAX;
        auto check = [&](int index)->bool {
            double time = 0;
            for (int i = 0; i < dist.size() - 1; i++) {
                time += ceil((double)dist[i] / index);
            }
            time += (double)dist.back() / index;

            return time <= hour;
        };
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (check(mid)) {
                right = mid;
            }
            else {
                left = mid + 1;
            }
        }

        return left;
    }
};

原文作者：F_JustWei

原文链接：http://139.196.79.90/2021/05/23/5764-%E5%87%86%E6%97%B6%E5%88%B0%E8%BE%BE%E7%9A%84%E5%88%97%E8%BD%A6%E6%9C%80%E5%B0%8F%E6%97%B6%E9%80%9F/

发表日期：May 23rd 2021, 12:37:06 pm

更新日期：May 23rd 2021, 1:25:03 pm

Next Post

5765. 跳跃游戏 VII
Previous Post

5763. 哪种连续子字符串更长

CATALOG

1. 5764. 准时到达的列车最小时速

