题目描述

在一个水平直线上，有N个加油站，位置分别在stations[0], stations[1], …, stations[N-1]。现在可以添加K个加油站到直线上任意位置，求添加K个加油站后，加油站的最小的最大距离是多少。

样例

Input: stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K = 9
Output: 0.500000

算法1

二分法 $O(nlogM)$ M为二分的范围

对添加K个加油站后最小的最大距离进行二分，二分的范围为start=0, end=10^9。如果添加K个加油站后，加油站之间的最大距离能减小到x，则结果的范围为[x, end]；否则为[start, x]

时间复杂度分析：$O(nlogM)$，二分的复杂度为logM，判断当前最小的最大距离是否合法的复杂度为n

Java 代码

class Solution {
    public double minmaxGasDist(int[] stations, int K) {
        double s=0, e=10e9;
        while(e-s>1e-8) {
            double mid = (s+e)/2;
            if(checkMin(stations, mid, K)<0) s=mid;
            else e=mid;
        }
        return s;
    }


    private int checkMin(int[] stations, double dist, int k) {
        for(int i=1; i<stations.length; i++) {
            double gap = (double)(stations[i] - stations[i-1]);
            if(gap>dist) {
                k-=(int)(gap/dist);
                if(gap%dist==0) k--;
            }
        }
        return k;
    }
}