题目描述：

LeetCode 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.

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

Pingbacks已关闭。