69 - 774. Minimize Max Distance to Gas Station

On a horizontal number line, we have gas stations at positions stations[0], stations[1], ..., 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.

Code in C++:

double minmaxGasDist(vector<int>& st, int K) {
    int count, N = st.size();
    float left = 0, right = st[N - 1] - st[0], mid;
    while (left + 0.00001 < right) {
        mid = (left + right) / 2;
        count = 0;
        for (int i = 0; i < N - 1; ++i)
            count += ceil((st[i + 1] - st[i]) / mid) - 1;
        if (count > K) left = mid;
        else right = mid;
    }
    return right;
}

注解：
二分法：
1）left=0，right=已有的站从头到尾的总距离，left+0.00001<right时结果满足要求。
2）mid=(left+right)/2，计算以此mid作为最大间距时两站之间需要插入几个点，若大于K，说明mid取小了，令left=mid，反之令right=mid。

Discuss地址：
https://discuss.leetcode.com/category/1739/minimize-max-distance-to-gas-station