文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 模擬超時
    • 2.2 二分查找

1. 題目

給你一個浮點數(shù) hour ，表示你到達(dá)辦公室可用的總通勤時間。
要到達(dá)辦公室，你必須按給定次序乘坐 n 趟列車。
另給你一個長度為 n 的整數(shù)數(shù)組 dist ，其中 dist[i] 表示第 i 趟列車的行駛距離（單位是千米）。

每趟列車均只能在整點發(fā)車，所以你可能需要在兩趟列車之間等待一段時間。

例如，第 1 趟列車需要 1.5 小時，那你必須再等待 0.5 小時，搭乘在第 2 小時發(fā)車的第 2 趟列車。
返回能滿足你準(zhǔn)時到達(dá)辦公室所要求全部列車的 最小正整數(shù) 時速（單位：千米每小時），如果無法準(zhǔn)時到達(dá)，則返回 -1 。

生成的測試用例保證答案不超過 10^7 ，且 hour 的 小數(shù)點后最多存在兩位數(shù)字 。

示例 1： 輸入：dist = [1,3,2], hour = 6 輸出：1 解釋：速度為 1 時： - 第 1 趟列車運行需要 1/1 = 1 小時。 - 由于是在整數(shù)時間到達(dá)，可以立即換乘在第 1 小時發(fā)車的列車。第 2 趟列車運行需要 3/1 = 3 小時。 - 由于是在整數(shù)時間到達(dá)，可以立即換乘在第 4 小時發(fā)車的列車。第 3 趟列車運行需要 2/1 = 2 小時。 - 你將會恰好在第 6 小時到達(dá)。示例 2： 輸入：dist = [1,3,2], hour = 2.7 輸出：3 解釋：速度為 3 時： - 第 1 趟列車運行需要 1/3 = 0.33333 小時。 - 由于不是在整數(shù)時間到達(dá)，故需要等待至第 1 小時才能搭乘列車。第 2 趟列車運行需要 3/3 = 1 小時。 - 由于是在整數(shù)時間到達(dá)，可以立即換乘在第 2 小時發(fā)車的列車。第 3 趟列車運行需要 2/3 = 0.66667 小時。 - 你將會在第 2.66667 小時到達(dá)。示例 3： 輸入：dist = [1,3,2], hour = 1.9 輸出：-1 解釋：不可能準(zhǔn)時到達(dá)，因為第 3 趟列車最早是在第 2 小時發(fā)車。提示： n == dist.length 1 <= n <= 10^5 1 <= dist[i] <= 10^5 1 <= hour <= 10^9 hours 中，小數(shù)點后最多存在兩位數(shù)字

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-speed-to-arrive-on-time
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

類似題目：LeetCode 1231. 分享巧克力（極小極大化 二分查找）

2.1 模擬超時

51 / 53 個通過測試用例

class Solution { public:int minSpeedOnTime(vector<int>& dist, double hour) {int n = dist.size();if(n > ceil(hour))return -1;long s = 0;for(int i = 0; i < n; ++i)s += dist[i];int v = s/hour-1;if(v <= 0) v = 1;while(1){double t = 0;for(int i = 0; i < n-1; ++i){ t += ceil(dist[i]/double(v));}t += dist.back()/double(v);if(t <= hour)break;v++;}return v;} };

2.2 二分查找

v 的增加，總得到達(dá)時間不會變多，具有單調(diào)性，采用二分查找

class Solution { public:int minSpeedOnTime(vector<int>& dist, double hour) {int n = dist.size();if(n > ceil(hour))return -1;int l = 1, r = 1e9, ans, v;while(l <= r){v = (l+r)>>1;double t = 0;for(int i = 0; i < n-1; ++i)t += ceil(dist[i]/double(v));t += dist.back()/double(v);if(t <= hour){ans = v;r = v-1;}elsel = v+1;}return ans;} };

308 ms 98.8 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1870. 准时到达的列车最小时速（二分查找）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。