# 774. Minimize Max Distance to Gas Station

On a horizontal number line, we have gas stations at positions `stations[0], stations[1], ..., stations[N-1]`, where `N = stations.length`.

Now, we add `K` more gas stations so that D, the maximum distance between adjacent gas stations, is minimized.

Return the smallest possible value of D.

Example:

``````Input: stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K = 9
Output: 0.500000
``````

Note:

1. `stations.length` will be an integer in range `[10, 2000]`.
2. `stations[i]` will be an integer in range `[0, 10^8]`.
3. `K` will be an integer in range `[1, 10^6]`.
4. Answers within `10^-6` of the true value will be accepted as correct.

[10, 19, 25, 27, 56, 63, 70, 87, 96, 97]，K = 3

9，6，2，29，7，7，17，9，1

``````class Solution {
public:
double minmaxGasDist(vector<int>& stations, int K) {
double left = 0, right = 1e8;
while (right - left > 1e-6) {
double mid = left + (right - left) / 2;
if (helper(stations, K, mid)) right = mid;
else left = mid;
}
return left;
}
bool helper(vector<int>& stations, int K, double mid) {
int cnt = 0, n = stations.size();
for (int i = 0; i < n - 1; ++i) {
cnt += (stations[i + 1] - stations[i]) / mid;
}
return cnt <= K;
}
};
``````

``````class Solution {
public:
double minmaxGasDist(vector<int>& stations, int K) {
double left = 0, right = 1e8;
while (right - left > 1e-6) {
double mid = left + (right - left) / 2;
int cnt = 0, n = stations.size();
for (int i = 0; i < n - 1; ++i) {
cnt += (stations[i + 1] - stations[i]) / mid;
}
if (cnt <= K) right = mid;
else left = mid;
}
return left;
}
};
``````

Find K-th Smallest Pair Distance

Kth Smallest Number in Multiplication Table

Maximum Average Subarray II

Kth Smallest Element in a Sorted Matrix

https://leetcode.com/problems/minimize-max-distance-to-gas-station/solution/

https://leetcode.com/problems/minimize-max-distance-to-gas-station/discuss/113629/Approach-the-problem-using-the-%22trial-and-error%22-algorithm

https://leetcode.com/problems/minimize-max-distance-to-gas-station/discuss/113633/Easy-and-Concise-Solution-using-Binary-Search-C++JavaPython

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation