0774：最小化去加油站的最大距离（★★）

力扣第 774 题

题目

整数数组 stations 表示 水平数轴 上各个加油站的位置。给你一个整数 k 。

请你在数轴上增设 k 个加油站，新增加油站可以位于 水平数轴 上的任意位置，而不必放在整数位置上。

设 penalty() 是：增设 k 个新加油站后，相邻 两个加油站间的最大距离。

示例 1：

输入：stations = [1,2,3,4,5,6,7,8,9,10], k = 9
输出：0.50000

示例 2：

输入：stations = [23,24,36,39,46,56,57,65,84,98], k = 1
输出：14.00000

提示：

• 10 <= stations.length <= 2000
• 0 <= stations[i] <= 108
• stations 按 严格递增 顺序排列
• 1 <= k <= 106

分析

• 二分答案即可

解答

1
2
3
4
5
6
7

class Solution:
    def minmaxGasDist(self, stations: List[int], k: int) -> float:
        def check(x):
            return sum((b-a-1)//x for a,b in pairwise(A))<=k

        A = [x*10**6 for x in stations]
        return bisect_left(range(A[-1]-A[0]),True,1,key=check) / 10**6 

302 ms