Problem#
可以花 hour 小時通勤到辦公室，必須要按照順序搭繩 n 輛火車，並給你 dist[i] 長度 n 代表第 i 輛火車要搭幾公里
每輛列車必須在整點出發，問你能不能回傳一個最小的速度搭完所有的火車，回傳 -1 代表不可能準時到達。
測資限制#
- $1 \le n \le 10^5$
- $1 \le dist[i] \le 10^5$
- $1 \le hour \le 10^9$
- 保證答案不超過 $10^7$，且
hour會給到小數第二位
想法#
對於速度 $i$ 來說，我們可以求出在這個速度下要花多久時間才能搭完全部的車站 $f(i)$
接著可以發現如果從可以到達與否的角度來看 $i$ 的話，當 $f(i) <= \text{hour}$ 的時候，代表可以準時到達
可以發現我們要找的就是第一個 OK 的速度，二分答案
1 | // 第二個範例輸入 |
- 時間複雜度: $\mathcal{O}(\log{n})$
- 空間複雜度: $\mathcal{O}(1)$