Skip to content

Latest commit

 

History

History
 
 

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

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

解法1:贪心法

贪心法有非常巧妙的思想,这里用到了pq.

首先我们将所有老加油站之间的间隔距离放入pq,默认是大顶堆,这些老加油站的间隔都没有新加油站插入。那么,对于队首的这个间距最大,说明我们要对其下手,先尝试将这个间距除以2,这里除以2表明原本是没有新加油站的,现在加入一个。然后将这个新间隔放入队列。

每次我们取队首元素,总是得到的是(当前最大的)某两个老加油站之间的新间隔,以及这两个老加油站之间插入的新加油站数量m。我们需要做的,是重新规划这两个老加油站之间的间隔,改成插入的新加油站数量为m+1.

重复上述过程,直至加入新加油站的总是达到了K。此时队首的老加油站之间的新间距,就是整体最大的间距。

这个方法非常巧妙,只可惜仍然超时。

解法2:二分法

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

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

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

Leetcode Link