LeetCode 774. 最小化去加油站的最大距离（极小极大化 二分查找）

示例：
输入：stations = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], K = 9
输出：0.500000

注：
stations.length 是在范围 [10, 2000] 内的整数
stations[i] 是在范围 [0, 10^8] 内的整数
K 是在范围 [1, 10^6] 内的整数
在 10^-6 以内的正确值会被视为正确的答案

class Solution {
public:
    double minmaxGasDist(vector<int>& stations, int K) {
    	int n = stations.size();
    	vector<int> dis(n-1);
    	for(int i = 1; i < n; ++i)
    	{
    		dis[i-1] = stations[i]-stations[i-1];//加油站之间的距离
    	}
    	double l = 0, r = 1e8+1, d, ans;
    	while(r-l >= 1e-7)
    	{
    		d = (l+r)/2.0;
    		if(isok(dis,d,K))
    		{
    			r = d;
    			ans = d;
    		}
    		else
    			l = d;
    	}
    	return ans;
    }

    bool isok(vector<int>& dis, double d, int K)
    {	//每个站之间的相邻距离为 d, 增加 K 个站够吗？
    	int need = 0;
    	for(int i = 0; i < dis.size(); ++i)
    	{
    		need += ceil(dis[i]/d)-1;
    	}
    	return need <= K;
    }
};