LC 774. Minimize Max Distance to Gas Station 【lock，hard】

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.

也是用了二分查找，找的是中位数。

Runtime:28ms Beats: 81.77%

class Solution {

public:

    double minmaxGasDist(vector<int>& stations, int K) {

        double left = 0.0, right = 1000000.0, mid = 0.0;

        while (left + 0.0000001 < right) {

            mid = left + (right - left) / 2.0;

            int cnt = ;

            for (int i = ; i < stations.size() - ; i++) {

                cnt += (stations[i + ] - stations[i]) / mid;

            }

            if (cnt <= K) right = mid;

            else left = mid;

        }

        return left;

    }

};

巴特西

LC 774. Minimize Max Distance to Gas Station 【lock，hard】

最新文章

热门文章