[LeetCode]Minimize Max Distance to Gas Station

题目描述:

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.

题目大意:

给定一组加油站的位置stations,在这些加油站中新增K个加油站,使得相邻加油站之间的最大距离最小化。

求最小化的最大距离。

解题思路:

二分枚举答案(Binary Search)

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

 

本文链接:http://bookshadow.com/weblog/2018/01/28/leetcode-minimize-max-distance-to-gas-station/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

暂无评论

张贴您的评论