主題
題目連結(jié)：
題目意譯：
你被給定一個(gè)浮點(diǎn)數(shù)數(shù)字 hour ，代表著你到達(dá)辦公室的時(shí)限。為了通勤到辦公室，你必須依序地搭 n 臺(tái)火車(chē)。你同樣地也被給定一個(gè)長(zhǎng)度 n 的整數(shù)陣列 dist ，其中 dist[i] 代表著第 i 臺(tái)火車(chē)的乘車(chē)距離。
每臺(tái)火車(chē)只會(huì)於整數(shù)小時(shí)的時(shí)間點(diǎn)發(fā)車(chē)，所以你可能需要在兩次乘車(chē)之間等待。
例如，如果第 1 臺(tái)火車(chē)花費(fèi) 1.5 小時(shí)，則你必須多等額外 0.5 小時(shí)才能在 2 小時(shí)整的時(shí)間點(diǎn)搭上第 2 班火車(chē)並發(fā)車(chē)。
回傳最小可能的正整數(shù)速度 speed （每小時(shí)公里數(shù)），其代表每臺(tái)火車(chē)必須行駛之速度使得你可以準(zhǔn)時(shí)抵達(dá)辦公室；或是 -1 ，如果不可能準(zhǔn)時(shí)抵達(dá)。
測(cè)試資料之產(chǎn)生滿(mǎn)足答案不過(guò)超過(guò) 10 ^ 7 且 hour 最多只會(huì)在小數(shù)點(diǎn)後有兩位數(shù)字。
限制：
n == dist.length
1 ≦ n ≦ 10 ^ 5
1 ≦ dist[i] ≦ 10 ^ 5
1 ≦ hour ≦ 10 ^ 9
最多只會(huì)有兩位數(shù)字位於 hour 的小數(shù)點(diǎn)後。
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： dist = [1,3,2], hour = 6
輸出： 1
解釋?zhuān)?在速度 1 下：
- 第一臺(tái)火車(chē)耗時(shí) 1 ÷ 1 = 1 小時(shí)。
- 因?yàn)槲覀円呀?jīng)位於整數(shù)小時(shí)，我們便立即於 1 小時(shí)時(shí)間點(diǎn)發(fā)車(chē)。第二臺(tái)火車(chē)耗時(shí) 3 ÷ 1 = 3 小時(shí)。
- 因?yàn)槲覀円呀?jīng)位於整數(shù)小時(shí)，我們便立即於 4 小時(shí)時(shí)間點(diǎn)發(fā)車(chē)。第三臺(tái)火車(chē)耗時(shí) 2 ÷ 1 = 2 小時(shí)。
- 你將恰好抵達(dá)於 6 小時(shí)之時(shí)間點(diǎn)。
範(fàn)例 2：
輸入： dist = [1,3,2], hour = 2.7
輸出： 3
解釋?zhuān)?在速度 3 下：
- 第一臺(tái)火車(chē)耗時(shí) 1 ÷ 3 = 0.33333 小時(shí)。
- 因?yàn)槲覀儾晃混墩麛?shù)小時(shí)上，所以我們等到 1 小時(shí)時(shí)間點(diǎn)發(fā)車(chē)。第二臺(tái)火車(chē)耗時(shí) 3 ÷ 3 = 1 小時(shí)。
- 因?yàn)槲覀円呀?jīng)位於整數(shù)小時(shí)，我們便立即於 2 小時(shí)時(shí)間點(diǎn)發(fā)車(chē)。第三臺(tái)火車(chē)耗時(shí) 2 ÷ 3 = 0.66667 小時(shí)。
- 你將抵達(dá)於 2.66667 小時(shí)之時(shí)間點(diǎn)。
範(fàn)例 3：
輸入： dist = [1,3,2], hour = 1.9
輸出： -1
解釋?zhuān)?不可能準(zhǔn)時(shí)抵達(dá)，因?yàn)榈谌_(tái)火車(chē)最早能發(fā)車(chē)的時(shí)間點(diǎn)為 2 小時(shí)整。
解題思維：
對(duì)於每個(gè)上界 U （因?yàn)轭}目保證，所以一開(kāi)始可以設(shè)為 10 ^ 7 + 1）、下界 L（一開(kāi)始設(shè)為 1）之中間值 M = (U + L) ÷ 2 ，當(dāng)作一個(gè)可能的 speed 。然後我們?nèi)ピ囋嚳?M 值是否可行。如果可行，便將上界降低到變?yōu)?M ；反之，將下界提高到變?yōu)?M + 1。
重複以上步驟直到 L = U 為止（答案收斂）。此時(shí)的 L 值即為所求。不過(guò)當(dāng)過(guò)程中不管套入什麼 M 值都不可行，則代表著不可能準(zhǔn)時(shí)抵達(dá)，此時(shí)回傳 -1 。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
