5764.準(zhǔn)時(shí)到達(dá)的列車(chē)最小時(shí)速
難度：中等
題目：
給你一個(gè)浮點(diǎn)數(shù) hour 您朽，表示你到達(dá)辦公室可用的總通勤時(shí)間狂丝。要到達(dá)辦公室，你必須按給定次序乘坐 n 趟列車(chē)哗总。另給你一個(gè)長(zhǎng)度為 n 的整數(shù)數(shù)組 dist 几颜，其中 dist[i] 表示第 i 趟列車(chē)的行駛距離（單位是千米）。
每趟列車(chē)均只能在整點(diǎn)發(fā)車(chē)讯屈，所以你可能需要在兩趟列車(chē)之間等待一段時(shí)間蛋哭。
例如，第 1 趟列車(chē)需要 1.5 小時(shí)涮母，那你必須再等待 0.5 小時(shí)谆趾，搭乘在第 2 小時(shí)發(fā)車(chē)的第 2 趟列車(chē)躁愿。
返回能滿(mǎn)足你準(zhǔn)時(shí)到達(dá)辦公室所要求全部列車(chē)的 最小正整數(shù) 時(shí)速（單位：千米每小時(shí)），如果無(wú)法準(zhǔn)時(shí)到達(dá)沪蓬，則返回 -1 彤钟。
生成的測(cè)試用例保證答案不超過(guò) 107 ，且 hour 的 小數(shù)點(diǎn)后最多存在兩位數(shù)字 怜跑。
提示：
- n == dist.length
- 1 <= n <= 10**5
- 1 <= dist[i] <= 10 ** 5
- 1 <= hour <= 10 ** 9
- hours 中样勃，小數(shù)點(diǎn)后最多存在兩位數(shù)字
示例：
示例 1：
輸入：dist = [1,3,2], hour = 6
輸出：1
解釋?zhuān)核俣葹?1 時(shí)：
- 第 1 趟列車(chē)運(yùn)行需要 1/1 = 1 小時(shí)。
- 由于是在整數(shù)時(shí)間到達(dá)性芬，可以立即換乘在第 1 小時(shí)發(fā)車(chē)的列車(chē)峡眶。第 2 趟列車(chē)運(yùn)行需要 3/1 = 3 小時(shí)。
- 由于是在整數(shù)時(shí)間到達(dá)植锉，可以立即換乘在第 4 小時(shí)發(fā)車(chē)的列車(chē)辫樱。第 3 趟列車(chē)運(yùn)行需要 2/1 = 2 小時(shí)。
- 你將會(huì)恰好在第 6 小時(shí)到達(dá)俊庇。
示例 2：
輸入：dist = [1,3,2], hour = 2.7
輸出：3
解釋?zhuān)核俣葹?3 時(shí)：
- 第 1 趟列車(chē)運(yùn)行需要 1/3 = 0.33333 小時(shí)狮暑。
- 由于不是在整數(shù)時(shí)間到達(dá)，故需要等待至第 1 小時(shí)才能搭乘列車(chē)辉饱。第 2 趟列車(chē)運(yùn)行需要 3/3 = 1 小時(shí)搬男。
- 由于是在整數(shù)時(shí)間到達(dá)，可以立即換乘在第 2 小時(shí)發(fā)車(chē)的列車(chē)彭沼。第 3 趟列車(chē)運(yùn)行需要 2/3 = 0.66667 小時(shí)缔逛。
- 你將會(huì)在第 2.66667 小時(shí)到達(dá)。
示例 3：
輸入：dist = [1,3,2], hour = 1.9
輸出：-1
解釋?zhuān)翰豢赡軠?zhǔn)時(shí)到達(dá)姓惑，因?yàn)榈?3 趟列車(chē)最早是在第 2 小時(shí)發(fā)車(chē)褐奴。
分析
這道題簡(jiǎn)直太符合每天卡點(diǎn)簽到的我了，從7點(diǎn)55出門(mén)開(kāi)始于毙，一直優(yōu)化到現(xiàn)在每天8點(diǎn)25風(fēng)一般的卡點(diǎn)簽到敦冬，哈哈。
這道題看到10**7唯沮，不用想就是二分脖旱，否則肯定超時(shí)！除了二分查找的時(shí)間優(yōu)化介蛉，解題過(guò)程中有哪些優(yōu)化點(diǎn)呢夯缺？
幾點(diǎn)優(yōu)化
-
客車(chē)每個(gè)整點(diǎn)發(fā)車(chē)
由于每趟列車(chē)乘坐的長(zhǎng)度不同，需要我們對(duì)速度除以距離后取整甘耿。python整數(shù)相除取整公式一定要記子欢怠：
被除數(shù) + 除數(shù) - 1 // 除數(shù)，只要整數(shù)多1佳恬，就可以保證向上取整了捏境。 -
至少需要的小時(shí)數(shù)
由于列車(chē)整點(diǎn)出發(fā)于游，所以速度哪怕無(wú)窮大，前n-1車(chē)座列車(chē)最少也需要n-1個(gè)小時(shí)垫言，
最后一次列車(chē)可以忽略到無(wú)窮小贰剥。那么hour 如何小于 len(dist) -1 則肯定無(wú)法抵達(dá)。 -
二分的最大值是多少筷频？
二分查找需要設(shè)置最小值和最大值蚌成，然后進(jìn)行二分操作，這道題的最大值該如何取凛捏，10**9嗎担忧？那你要多算多少次啊坯癣！
由于題目說(shuō)了瓶盛，hour小數(shù)最多存在兩位，也就是最快0.01示罗，那么右端點(diǎn)只需設(shè)置max(dist) * 100就能滿(mǎn)足題意惩猫。
這樣會(huì)比 10 ** 9時(shí)間復(fù)雜度降低很多！
最后需要注意一點(diǎn)蚜点，hour的小數(shù)是怎么來(lái)的轧房？因?yàn)榍皀-1次列車(chē)都是整點(diǎn)出發(fā)，所以小數(shù)是通過(guò)最后一趟列車(chē)來(lái)的绍绘！
下車(chē)后就認(rèn)為到達(dá)終點(diǎn)了(地鐵里打卡的騷操作奶镶？)。所以二分只循環(huán)計(jì)算前n-1脯倒，最后一次直接除保留小數(shù)实辑。
理解了上面這些內(nèi)容捺氢，這道題就變的很簡(jiǎn)單了藻丢，但Python的效率注定再怎么優(yōu)化，耗時(shí)也渣的不行摄乒，尤其在大的數(shù)據(jù)量上更為明顯悠反。
來(lái)看看解題吧。
解題：
class Solution:
def minSpeedOnTime(self, dist, hour):
# 如果時(shí)間小于dist -1返回 -1
if hour < len(dist) - 1:
return -1
# 設(shè)置二分查找邊界
left,right = 1, max(dist) * 100
while left < right:
cost, mid = 0, (left + right) // 2
for i in dist[:-1]:
cost += (i + mid - 1) // mid
# 如果cost已經(jīng)大于hour馍佑，直接left移位斋否，重新計(jì)算
if cost > hour:
left = mid + 1
continue
# 單獨(dú)計(jì)算最后一次的耗時(shí)
cost += dist[-1] / mid
if cost > hour:
left = mid + 1
else:
right = mid
return -1 if left == 10 ** 9 else left
歡迎關(guān)注我的公眾號(hào): 清風(fēng)Python，帶你每日學(xué)習(xí)Python算法刷題的同時(shí)拭荤，了解更多python小知識(shí)茵臭。
我的個(gè)人博客：https://qingfengpython.cn
