Readme

774.Minimize-Max-Distance-to-Gas-Station

解法1：贪心法

贪心法有非常巧妙的思想，这里用到了大顶堆的优先对了. 队列里放置的是{space, parts}，表示有连续parts个长度为space的区间。注意，space*parts其实代表的一定是某两个加油站之间的距离。最开始时，我们放入所有的{stations[i]-stations[i-1], 1}。

如果我们还有增加加油站的名额，那么必然是对PQ的队首元素{space, parts}操作，试图将当前全局最大的这个space降下来。我们只需要试图在space*parts这个区段里再增加一个。于是我们弹出队首元素之后，再往PQ里放入{space*parts/(parts+1), parts+1}即可。

重复上述过程，直至我们用完了所有新增加油站的配额。此时队首元素的space，就是当前最大的新加油站的间距。

这个方法非常巧妙，只可惜仍然超时。这里有一个改进的方法。我们可以知道，如果所有的旧加油站不存在的话，那么我们直接可以得到最优的最大间距，即平分整个数轴，得到ub = (stations.back()-stations[0])/(K+1)。现在由于这些旧加油站的存在，可以帮助我们将最大间距变得更小。所以对于任意两个旧加油站之间的dist，我们至少应该拆分为dist/ub个parts，使得细分的space先一步到位直接逼近ub，也就是提前预定了一些新加油站的数目。这样可以提高效率，避免对新加油站一个一个的配置。

解法2：二分法

可以得到的最大间距d，下限是0，上限是原本最大的老加油站之间的间距。

不断二分尝试这个d，计算为了使得每个老加油站之间的新间距变为d，需要新加入多少新加油站。如果新加油站总数超过了K，说明这个d太小；否则可以继续尝试减小d，

最后知道二分的搜索精度小于1e-6.

Leetcode Link