leetcode 2187. Minimum Time to Complete Trips(完成行程的最短时间)
创始人
2024-05-30 04:35:10
0

(Medium)
在这里插入图片描述
time数组里面是每个bus完成一次路程需要的时间,假设时间单位是h, 比如time = [1,2,3]就表示第1辆bus跑完路程需要1h,第2辆需要2h,第3辆需要3h.
那么把所有bus都考虑进来,总共要跑完totalTrips次路程,问至少需要多少时间。
假设bus之间是独立的,不需要中间休息,可以连续运行。

思路:

先理解一下想要干什么。

比如Example 1, time = [1,2,3], totalTrips=5,
就是说3辆bus都一起跑,总共跑完5次需要最短的时间。

假设时间单位是h吧,
第1h,第1辆bus跑完1次,第2辆0次,第3辆0次,所以是[1,0,0]
第2h,第1辆2次,第2辆1次,第3辆还是0次,所以是[2,1,0]
第3h,第1辆3次,第2辆1次,第3辆1次,是[3,1,1], 总共完成了5次trip, 所以需要的时间是3h。

现在来推广,假设需要的时间是 T(h),
那么总共的次数 n = T/time1 + T/time2 + T/time3,
如果 n == totalTrips, 那么T就是所需的时间。

那如何找最小的T呢,就是不断调小T,让它仍然能满足 n == totalTrips,

为什么可以调小T但仍然能满足呢
假如time = [2,2,3], totalTrips = 5,
如果T=5,n=5/2+ 5/2 + 5/3 = 2+2+1 = 5,
调小T=4, 是不是仍然满足n = 4/2 + 4/2 + 4/3 = 2+2+1 = 5.
再调T=3, n = 3/2 + 3/2 + 3/3 = 3不满足,所以最小时间是4.

那么再考虑一下所需的最长时间(右边界)是多少呢?
就取最小的time, 让耗时最小的bus跑totalTrips次,那么耗时=min time ✖ totalTrips.

所以有没有熟悉的感觉,知道左边界是min time(最短可能的时间),右边界是min time ✖ totalTrips,
在这之间调整T,让 n == totalTrips.
用到binary search.

和以前binary search不同的是,当 n == totalTrips时,不要立刻返回mid,
因为上面也证实了,T还可以进一步调小,直到不能满足为止。

    public long minimumTime(int[] time, int totalTrips) {int n = time.length;long maxTime = 0;long minTime = Integer.MAX_VALUE;for(int curTime : time) {minTime = Math.min(minTime, curTime);maxTime = Math.max(maxTime, curTime);}if(totalTrips == 1) return minTime;long left = minTime;long right = totalTrips * minTime;while(left <= right) {long mid = left + (right - left) / 2;long cnt = 0;for(int curTime : time) {cnt += mid / curTime;if(cnt > totalTrips) break;}if(cnt >= totalTrips) right = mid - 1;else left = mid + 1;}return left;}

相关内容

热门资讯

美国不提安卓系统华为,迈向自主... 华为与美国:一场关于技术、市场与政策的较量在当今这个数字化的世界里,智能手机已经成为我们生活中不可或...
安卓系统怎么打开ppt,选择文... 你有没有遇到过这种情况:手里拿着安卓手机,突然需要打开一个PPT文件,却怎么也找不到方法?别急,今天...
谷歌退回到安卓系统,探索创新未... 你知道吗?最近科技圈可是炸开了锅,谷歌竟然宣布要退回到安卓系统!这可不是一个简单的决定,背后肯定有着...
安卓系统待机耗电多少,深度解析... 你有没有发现,手机电量总是不经用?尤其是安卓系统,有时候明明没怎么用,电量就“嗖”的一下子就下去了。...
小米主题安卓原生系统,安卓原生... 亲爱的手机控们,你是否曾为手机界面单调乏味而烦恼?想要给手机换换“衣服”,让它焕然一新?那就得聊聊小...
voyov1安卓系统,探索创新... 你有没有发现,最近你的手机是不是变得越来越流畅了?没错,我要说的就是那个让手机焕发青春的Vivo V...
电脑刷安卓tv系统,轻松打造智... 你有没有想过,家里的安卓电视突然变得卡顿,反应迟钝,是不是时候给它来个“大保健”了?没错,今天就要来...
安卓系统即将要收费,未来手机应... 你知道吗?最近有个大消息在科技圈里炸开了锅,那就是安卓系统可能要开始收费了!这可不是开玩笑的,这可是...
雷凌车载安卓系统,智能出行新体... 你有没有发现,现在的汽车越来越智能了?这不,我最近就体验了一把雷凌车载安卓系统的魅力。它就像一个聪明...
怎样拍照好看安卓系统,轻松拍出... 拍照好看,安卓系统也能轻松搞定!在这个看脸的时代,拍照已经成为每个人生活中不可或缺的一部分。无论是记...
安卓车机系统音频,安卓车机系统... 你有没有发现,现在越来越多的汽车都开始搭载智能车机系统了?这不,咱们就来聊聊安卓车机系统在音频方面的...
老苹果手机安卓系统,兼容与创新... 你手里那台老苹果手机,是不是已经陪你走过了不少风风雨雨?现在,它竟然还能装上安卓系统?这可不是天方夜...
安卓系统7.dns,优化网络连... 你有没有发现,你的安卓手机最近是不是有点儿“慢吞吞”的?别急,别急,让我来给你揭秘这可能与你的安卓系...
安卓手机系统怎么加速,安卓手机... 你有没有发现,你的安卓手机最近变得有点“慢吞吞”的?别急,别急,今天就来给你支几招,让你的安卓手机瞬...
小米note安卓7系统,探索性... 你有没有发现,手机更新换代的速度简直就像坐上了火箭呢?这不,小米Note这款手机,自从升级到了安卓7...
安卓和鸿蒙系统游戏,两大系统游... 你有没有发现,最近手机游戏界可是热闹非凡呢!安卓和鸿蒙系统两大巨头在游戏领域展开了一场激烈的较量。今...
安卓手机没有系统更,揭秘潜在风... 你有没有发现,现在安卓手机的品牌和型号真是五花八门,让人挑花了眼。不过,你知道吗?尽管市面上安卓手机...
充值宝带安卓系统,安卓系统下的... 你有没有发现,最近手机上的一款充值宝APP,在安卓系统上可是火得一塌糊涂呢!这不,今天就来给你好好扒...
安卓系统8.0镜像下载,轻松打... 你有没有想过,想要给你的安卓手机升级到最新的系统,却不知道从哪里下载那个神秘的安卓系统8.0镜像呢?...
安卓系统修改大全,全方位修改大... 你有没有想过,你的安卓手机其实是个大宝藏,里面藏着无数可以让你手机焕然一新的秘密?没错,今天就要来个...