774. Minimize Max Distance to Gas Station

给定排好序的一系列数，再其中插K个数，使得俩俩之间的最大距离最小。题目虽然带min-max，但不是博弈的题，和min-max无半毛关系。这题和Heaters场景有点像，都是对每个点找离它最近的点，不过heaters是对位置做二分，这道题是对最大距离的范围做二分。每次算出mid作为最大距离候选，然后数如果以mid为最大距离，需要新插入多少个数。如果所需的小于等于K，说明最大距离还可以再小点；反之则要再大点。

题目和答案参考自这。

class Solution {
public:
    double minmaxGasDist(vector<int>& stations, int K) {
        double start = 0, end = 1e8;
        const int N = stations.size();
        while (end - start > 1e-6) {
            double mid = start + (end - start) / 2;
            int cnt = 0;
            for (int i = 0; i < N - 1; ++i) {
                cnt += (stations[i + 1] - stations[i]) / mid;
            }
            if (cnt <= K) right = mid;
            else left = mid;
        }
        return left;
    }
};