Lintcode 848: Minimize Max Distance to Gas Station

https://www.lintcode.com/problem/minimize-max-distance-to-gas-station/description

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

Example 1:

Input：stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]，K = 9
Output：0.50
Explanation：The distance between adjacent gas stations is 0.50

Example 2:

Input：stations = [3,6,12,19,33,44,67,72,89,95]，K = 2
Output：14.00
Explanation：construction of gas stations at 86 locations

Notice

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

Notes:

This question can be solved by the binary search method.

Apparently, the question is asking for a min of maximum. Let say minMax, when val >= minMax, we can always finish one event; otherwise, it cannot be done. And val is apparently in a range.

So it is a binary search!

See the code below:

class Solution {
public:
    /**
     * @param stations: an integer array
     * @param k: an integer
     * @return: the smallest possible value of D
     */
    double minmaxGasDist(vector<int> &stations, int k) {
        // Write your code here
        sort(stations.begin(), stations.end());
        double epslon = 0.00001, left = epslon, right = stations.back();
        while(left + epslon < right) {
            double mid = left + (right - left) / 2;
            if(!isValid(stations, k, mid)) left = mid;
            else right = mid;
        }
        return left;
    }

private:
    bool isValid(vector<int>& gs, int k, double mid) {
        int ct = 0;
        double sum = 0;
        for(int i=0; i+1<gs.size(); ++i) {
            double dis = (double) (gs[i+1] - gs[i]);
            ct += (int)(dis/mid);
        }
        return ct <= k;
    }
};