贪心法有非常巧妙的思想,这里用到了pq.
首先我们将所有老加油站之间的间隔距离放入pq,默认是大顶堆,这些老加油站的间隔都没有新加油站插入。那么,对于队首的这个间距最大,说明我们要对其下手,先尝试将这个间距除以2,这里除以2表明原本是没有新加油站的,现在加入一个。然后将这个新间隔放入队列。
每次我们取队首元素,总是得到的是(当前最大的)某两个老加油站之间的新间隔,以及这两个老加油站之间插入的新加油站数量m。我们需要做的,是重新规划这两个老加油站之间的间隔,改成插入的新加油站数量为m+1.
重复上述过程,直至加入新加油站的总是达到了K。此时队首的老加油站之间的新间距,就是整体最大的间距。
这个方法非常巧妙,只可惜仍然超时。
可以得到的最大间距d,下限是0,上限是原本最大的老加油站之间的间距。
不断二分尝试这个d,计算为了使得每个老加油站之间的新间距变为d,需要新加入多少新加油站。如果新加油站总数超过了K,说明这个d太小;否则可以继续尝试减小d,
最后知道二分的搜索精度小于1e-6.