文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

假設(shè)我們?cè)谝粭l水平數(shù)軸上，列表 stations 來表示各個(gè)加油站的位置，加油站分別在 stations[0], stations[1], ..., stations[N-1] 的位置上，其中 N = stations.length。

現(xiàn)在我們希望增加 K 個(gè)新的加油站，使得相鄰兩個(gè)加油站的距離 D 盡可能的最小，請(qǐng)你返回 D 可能的最小值。

示例： 輸入：stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K = 9 輸出：0.500000注： stations.length 是在范圍 [10, 2000] 內(nèi)的整數(shù) stations[i] 是在范圍 [0, 10^8] 內(nèi)的整數(shù) K 是在范圍 [1, 10^6] 內(nèi)的整數(shù) 在 10^-6 以內(nèi)的正確值會(huì)被視為正確的答案

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

2. 解題

LeetCode 1231. 分享巧克力（極小極大化 二分查找）

• 模板題，預(yù)先求出每個(gè)站之間的距離，二分查找 d，檢查最小間距d下，K個(gè)站夠不夠

class Solution { public:double minmaxGasDist(vector<int>& stations, int K) {int n = stations.size();vector<int> dis(n-1);for(int i = 1; i < n; ++i){dis[i-1] = stations[i]-stations[i-1];//加油站之間的距離}double l = 0, r = 1e8+1, d, ans;while(r-l >= 1e-7){d = (l+r)/2.0;if(isok(dis,d,K)){r = d;ans = d;}elsel = d;}return ans;}bool isok(vector<int>& dis, double d, int K){ //每個(gè)站之間的相鄰距離為 d, 增加 K 個(gè)站夠嗎？int need = 0;for(int i = 0; i < dis.size(); ++i){need += ceil(dis[i]/d)-1;}return need <= K;} };

68 ms 13.3 MB

---

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

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

總結(jié)

以上是生活随笔為你收集整理的LeetCode 774. 最小化去加油站的最大距离（极小极大化 二分查找）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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