准时到达的列车最小时速 | Java刷题打卡-一一网

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

一、题目描述：

二、思路分析：

今天给大家分享的是一道本周力扣的周赛题目，题目的意思是给你一个通勤时间，一个每列列车行驶的距离数组，问你能保证准时到达公司的前提下，每列列车的最小时速可以是多少？需要注意的是每列列车只会在整点发车。说实话，看到这种题目，要求在满足某种条件下的最值，一般我们会考虑一下直接使用二分算法枚举所有可能的值，然后依次check每个值是否满足条件，满足条件的话再继续缩小区间。类似的思想的题目之前已经介绍过好几道了。回到本题，dist数组的数据量又正好是 10^5，nLogn直接搞定，符合我们的预期。

二分枚举每个可能的值。

确定了二分方法后，就需要确定枚举的上界和下界。
本题中枚举的下界是1，上界是10000000，因为题目中说了用例的答案不超过10000000.(这里我比赛在做的时候把边界想成了数组中的最大值和最小值，导致错误提交了几次才发现，坑~)
确定了边界后就是正常的枚举，对于每个mid值我们需要check以下当前值能不能准时到达公司。如果当前mid能够准时到达公司的话，那么我们可以把枚举的右边界right=mid;如果当前mid 不能够准时到达公司，那么我们需要提高速度，把左边界left = mid + 1;
当while循环结束的时候，left == right，因为可能存在无法准时到达的情况，所以我们需要check一下循环结束后指向的位置，如果能够到达，返回left即可。如果不能，返回-1.
然后就是check 函数的书写。check需要检查某个速度能不能准时到达公司，而且每列列车只在整点发车，到早了需要等待下一个整点，所以是不是就是上取整。是的。但是对于最后一个班次的列车，不需要取整操作，是多久到达就加多少时间。
至此，我们的题目就OK啦。

三、AC 代码：

class Solution {

    /**
     * @param Integer[] $dist
     * @param Float $hour
     * @return Integer
     */
    function minSpeedOnTime($dist, $hour) {
        $n = count($dist);
        $left = min($dist);
        $left = 1;
        // $right = max($dist);
        $right = 10000000;
        while ($left < $right) {
            $mid = $left + (int)(($right - $left) / 2);
            // echo $mid;
            if ($this->check($dist, $hour, $mid)) {
                $right = $mid;
            } else {
                $left = $mid + 1;
            }
        }
        
        if ($this->check($dist, $hour, $left)) {
            return $left;
        }
        return -1;
    }
    
    protected function check(&$dist, $hour, $speed)
    {
        $len_n = count($dist);
        $realtime = 0;
        for ($i = 0; $i < $len_n - 1; $i++) {
            $realtime += ceil($dist[$i] / $speed);
        }
        $realtime += ($dist[$i] / $speed);
        return $realtime <= $hour;
    }
}

复制代码