# [LeetCode] 774. Minimize Max Distance to Gas Station 最小化加油站间的最大距离

2021年09月15日 阅读数：1

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

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

Return the smallest possible value of D.python

Example:函数

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

Note:post

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.

Java:

```public double minmaxGasDist(int[] stations, int K) {
int n = stations.length;
double[] gap = new double[n - 1];
for (int i = 0; i < n - 1; ++i) {
gap[i] = stations[i + 1] - stations[i];
}
double lf = 0;
double rt = Integer.MAX_VALUE;
double eps = 1e-7;
while (Math.abs(rt - lf) > eps) {
double mid = (lf + rt) /2;
if (check(gap, mid, K)) {
rt = mid;
}
else {
lf = mid;
}
}
return lf;
}

boolean check(double[] gap, double mid, int K) {
int count = 0;
for (int i = 0; i < gap.length; ++i) {
count += (int)(gap[i] / mid);
}
return count <= K;
}　　```

Python:

```class Solution(object):
def minmaxGasDist(self, stations, K):
"""
:type stations: List[int]
:type K: int
:rtype: float
"""
def possible(stations, K, guess):
return sum(int((stations[i+1]-stations[i]) / guess)
for i in xrange(len(stations)-1)) <= K

left, right = 0, 10**8
while right-left > 1e-6:
mid = left + (right-left)/2.0
if possible(mid):
right = mid
else:
left = mid
return left　　```

Python:

```class Solution(object):
def minmaxGasDist(self, st, K):
"""
:type stations: List[int]
:type K: int
:rtype: float
"""
lf = 1e-6
rt = st[-1] - st[0]
eps = 1e-7
while rt - lf > eps:
mid = (rt + lf) / 2
cnt = 0
for a, b in zip(st, st[1:]):
cnt += (int)((b - a) / mid)
if cnt <= K: rt = mid
else: lf = mid
return rt　　```

Python:

```class Solution(object):
def minmaxGasDist(self, stations, K):
"""
:type stations: List[int]
:type K: int
:rtype: float
"""
stations.sort()
step = 1e-9
left, right = 0, 1e9
while left <= right:
mid = (left + right) / 2
if self.isValid(mid, stations, K):
right = mid - step
else:
left = mid + step
return mid
def isValid(self, gap, stations, K):
for x in range(len(stations) - 1):
dist = stations[x + 1] - stations[x]
K -= int(math.ceil(dist / gap)) - 1
return K >= 0　　```

C++:

```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;
}
};
```

C++:

```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;
}
};
```

719. Find K-th Smallest Pair Distance

668. Kth Smallest Number in Multiplication Table

644. Maximum Average Subarray II

378. Kth Smallest Element in a Sorted Matrix