本文主要是介绍Leetcode 774. Minimize Max Distance to Gas Station，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
LWC 69: 774. Minimize Max Distance to Gas Station
传送门：774. Minimize Max Distance to Gas Station
Problem:
On a horizontal number line, we have gas stations at positions stations[0], stations1, …, 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:
- stations.length will be an integer in range [10, 2000].
- stations[i] will be an integer in range [0, 10^8].
- K will be an integer in range [1, 10^6].
- Answers within 10^-6 of the true value will be accepted as correct.
思路：
首先求出每个station之间的距离，考虑如下问题：两个station为[1, 9]，gap为8。要插入一个station使得最大的最小，显然插入后应该为[1, 5, 9]，最大间隔为4。举个反例，如果插入后为[1, 6, 9], [1, 3, 9]，它们的最大间隔分别为5， 6，明显不是最小。从这里可以看出，对于插入k个station使得最大的最小的唯一办法是均分。
一种贪心的做法是，找到最大的gap，插入1个station，依此类推，但很遗憾，这种贪心策略是错误的。问题的难点在于我们无法确定到底哪两个station之间需要插入station，插入几个station也无法得知。
换个思路，如果我们假设知道了答案会怎么样？因为知道了最大间隔，所以如果目前的两个station之间的gap没有符合最大间隔的约束，那么我们就必须添加新的station来让它们符合最大间隔的约束，这样一来，对于每个gap我们是能够求得需要添加station的个数。如果需求数<=K，说明我们还可以进一步减小最大间隔，直到需求数>K。
Python版本：
class Solution(object):def minmaxGasDist(self, st, K):""":type stations: List[int]:type K: int:rtype: float"""lf = 1e-6rt = st[-1] - st[0]eps = 1e-7while rt - lf > eps:mid = (rt + lf) / 2cnt = 0for a, b in zip(st, st[1:]):cnt += (int)((b - a) / mid)if cnt <= K: rt = midelse: lf = midreturn rt
这篇关于Leetcode 774. Minimize Max Distance to Gas Station的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
