力扣774：Minimize Max Distance to Gas Station

Problem:

On a horizontal number line, we have gas stations at positions stations[0], stations1, …, stations[N-1], where N = stations.length.
Now, we add K more gas stations so that D, the maximum distance between adjacent gas stations, is minimized.
Return the smallest possible value of D.

Example:

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

Note:

stations.length will be an integer in range [10, 2000].
stations[i] will be an integer in range [0, 10^8].
K will be an integer in range [1, 10^6].
Answers within 10^-6 of the true value will be accepted as correct.

思路：

拿到题目的第一想法是用贪心法求解，每次选取距离最大的两个节点，然后再从之间插入新的节点，然而这种思路面临的问题是，首先我不知道在哪两个新的节点插入，要插多少个新的节点也无法得知。
换个想法，如果一开始我们已经知道了最大间隔是多少，那么我们就也就知道现在两个节点的间隔是不是满足最大间隔的要求，如果不满足，我们就必须添加新的节点来让他满足此要求，这样，对于每一个间隔，我们是知道需要添加的站点的数目的。如果总的添加数目小于K，证明我们还可以继续添加，直到添加的数目大于K为止。

(```
public class Solution {
public double minmaxGasDist(int[] stations, int k){
int len = stations.length;
int []temp = new int[len-1];
for(int i = 0; i < len-1; i++){
temp[i] = stations[i+1] - stations[i];
}
double lf = 0;
double rf = Integer.MAX_VALUE;
double eps = 1e-7;
while (Math.abs(rf- lf) > eps){
double mid = (rf + lf)/2;
if(check(temp, mid, k)){
rf = mid;
}else{
lf = mid;
}
}
return lf;
}

private boolean check(int[] gap, double mid, int k){
    int count = 0;
    for(int i = 0; i < gap.length; i++){
        count += (int)(gap[i]/mid);
    }
    return count < k;
}

}