leetcode：774. 最小化去加油站的最大距离【经典二分check】

题目截图

题目分析

• 最小化加油站间的最大距离
• 假设加油站间最大距离为x = 所有距离小于等于x
• x越小，越难达到
• 获得初始距离diff
• 然后check需要看看为了达到所右距离小于等于x，需要补充多少
• 假设需要need个，判断每个距离d
• 如果d <= x 无需加
• 如果d / x 为整数，则需要多加int(d / x) - 1
• 如果d / x为小数，需要多加int(d / x)
• x == 0为False特判
• 返回need <= k即可

ac code

class Solution:
    def minmaxGasDist(self, stations: List[int], k: int) -> float:
        # 最小最大值问题 = 二分
        diff = [b - a for a, b in pairwise(stations)]
        def check(x): # 有没有可能最大距离到达x
            # x越小越不可能
            # 保证所有距离小于等于x即可
            if x == 0:
                return False
            need = 0
            for d in diff:
                if d < x:
                    pass
                elif d / x == int(d / x):
                    need += int(d / x) - 1
                else:
                    need += int(d / x)
            return need <= k

            
        
        l, r = 10 ** (-6), 10 ** 9
        while r - l > 10 ** (-6):
            mid = (l + r) / 2
            if check(mid):# 最小mid可以达到
                r = mid
            else:
                l = mid
        return r
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

总结

• 涉及到小数的仍然可以二分
• 看l和r的差距即可
• 因为需要最小，所以满足后，需要让r = mid
• 经典最小最大 + 二分贪心模拟