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;}

相关内容

热门资讯

安卓系统的安全证书,守护移动安... 你知道吗?在咱们这个科技飞速发展的时代,手机已经成了我们生活中不可或缺的好伙伴。而说起手机,安卓系统...
谷歌安卓系统挣钱吗,如何通过它... 你有没有想过,那个无处不在的谷歌安卓系统,它到底是怎么赚钱的呢?没错,就是那个让我们的手机、平板、智...
GALGAME安卓换苹果系统,... 你有没有想过,那些在安卓手机上玩得如痴如醉的GALGAME,竟然也能在苹果系统上大放异彩?没错,就是...
华为宣布摆脱安卓系统,迈向自主... 哇,你知道吗?最近华为可是闹出了一个大新闻!那就是他们宣布要摆脱安卓系统,自己研发一套全新的操作系统...
安卓车机系统hcn,智能驾驶的... 你有没有发现,现在越来越多的汽车开始搭载智能化的车机系统了?这不,安卓车机系统HCN(Harmony...
超大平板安卓系统,创新体验与无... 你有没有想过,在这个科技飞速发展的时代,拥有一块超大平板电脑是多么酷炫的事情啊!想象那宽广的屏幕,无...
电脑装安卓系统步骤,电脑安装安... 你有没有想过,把安卓系统装在你的电脑上,是不是就像给电脑换了个新衣裳,瞬间变得时尚又实用呢?没错,今...
安卓系统视频存储软件,高效管理... 手机里的视频越来越多,是不是感觉存储空间不够用了?别急,今天就来给你安利几款安卓系统视频存储软件,让...
安卓系统如何连接奔驰,安卓系统... 你有没有想过,你的安卓手机和奔驰车之间也能来个亲密接触呢?没错,就是那种无缝连接的感觉,让你的手机和...
安卓系统emoji表情很少,探... 你知道吗?在手机世界里,emoji表情可是沟通的利器,它能让我们的聊天更加生动有趣。但是,你知道吗?...
安卓系统的德州游戏,刺激竞技体... 你有没有发现,安卓手机上的游戏世界越来越精彩了?尤其是那些德州游戏,简直让人停不下来!今天,就让我带...
xbox360安卓系统,探索跨... 你有没有想过,家里的老Xbox 360竟然也能变身成为安卓系统的超级玩家呢?没错,就是那个曾经陪伴我...
安卓系统怎么找云端,而是通过安... 你有没有想过,你的安卓手机里那些珍贵的照片、文件和笔记,其实都可以存放在云端,随时随地都能访问呢?没...
安卓手机系统更原装,深度解析原... 你有没有发现,用安卓手机的时候,有时候感觉系统就像是你从小到大最熟悉的那件衣服,穿在身上,舒服又自在...
安卓系统8怎样退回,安卓8.0... 你有没有遇到过这种情况:手机更新了安卓系统8,结果发现新系统里的某些功能让你觉得不适应,或者某些操作...
安卓系统好用的语音,智能生活新... 你有没有发现,现在手机里的语音助手越来越聪明了?尤其是安卓系统的语音功能,简直让人爱不释手!今天,就...
安卓系统应用禁用服务 你有没有发现,手机里的安卓系统应用有时候会偷偷地开启一些后台服务,这可真是让人头疼啊!今天,就让我来...
安卓拨打系统电话调用,轻松实现... 你有没有想过,当你手机里突然弹出一个电话,而你又恰好想打给某人时,安卓系统是怎么帮你完成这个神奇过程...
安卓系统转ios推荐,轻松过渡... 你是不是也和我一样,对手机系统有着浓厚的兴趣呢?最近,我发现了一个有趣的现象:越来越多的朋友从安卓系...
安卓系统ping ip地址,A... 你有没有想过,当你打开手机,输入一个IP地址,然后神奇地发现,你的安卓系统能够像魔法一样告诉你那个地...