【LeetCode】每日一题 2024_10_5 完成旅途的最少时间（二分答案）

前言

每天和你一起刷 LeetCode 每日一题~

大家国庆节快乐呀~

LeetCode 启动！

突然发现，国庆的每日一题，不是坐公交就是坐火车，不是坐火车就是做飞机，这就是你的国庆旅游计划吗！力扣！

题目：完成旅途的最少时间

代码与解题思路

国庆期间力扣居然连出了两道二分答案的题目，这道题相比上一题对我而言相对简单一些，前几天的那道题的浮点数控制还是有些难度的

不说题外话了，讲讲这道题有哪些需要注意的点：

1、如何找到二分答案的上下界？

下界通过看题目给出的数据范围即可，最小的总路程是 1，那最少花费的时间也只能是 1。

上界该如何判断呢？ 如果题目比较直接，那可以直接通过数据范围来设定，这道题显然不太容易判断出来，那我们就寻找一个极限的情况，假设 time 只有一个值 min，那我们最长需要的时间就是 totalTrips * min，time 如果增加其他元素，最后的答案时间会变小

也就是 totalTrips * min，就是题目能到达的最长时间，这样就能将他作为二分的上界了

2、check 函数的实现

二分题目的核心，不过这道题比较简单，直接遍历 time 数组，让 sum 累加当前的 totalTrips（即二分出来的 mid）/ time 的各个元素即可获得总的旅程数。

func minimumTime(time []int, totalTrips int) int64 {
    l, r := 1, totalTrips*slices.Min(time) // 二分的上下界
    for l < r {
        mid := (l+r)>>1
        sum := 0
        for _, v := range time {
            sum += mid/v
        }
        if sum < totalTrips {
            l = mid+1
        } else {
            r = mid
        }
    }
    return int64(l)
}

视频实况

【【LeetCode】每日一题 2024_10_5 完成旅途的最少时间（二分答案）】

每天进步一点点

可以和我刷一辈子的每日一题吗？
一题一题，积累起来就是一辈子。

原文地址：https://blog.csdn.net/Locky136/article/details/142712978

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！