在C ++中最小化到加油站的最大距离
假设我们有一条水平线。在该编号线上，我们在位置[0]，位置[1]，...，位置[N-1]处有加油站，其中N=位置数组的大小。现在，我们再添加K个加油站，以使相邻加油站之间的最大距离D最小。我们必须找到D的最小可能值。
因此，如果输入类似于测站=[1、2、3、4、5、6、7、8、9、10]，K=9，则输出将为0.5
为了解决这个问题，我们将遵循以下步骤-
定义一个函数ok()，它将使用x，数组v，
ret：=0
对于初始化i：=0，当i<v的大小时，更新（将i增加1），执行-
ret：=ret+（v[i+1]-v[i]）/x的上限
返回ret
从主要方法中执行以下操作-
低：=0
n：=s的大小
高：=s[n-1]-s[0]
而高-低>=1e-6时，执行-
高：=中
低：=中
中：=（低+高）/2.0
x：=ok(mid,s)
如果x>K，则-
除此以外
高回报
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int ok(double x, vector <int>& v){
int ret = 0;
for (int i = 0; i < v.size() - 1; i++) {
ret += ceil((v[i + 1] - v[i]) / x) - 1;
}
return ret;
}
double minmaxGasDist(vector<int>& s, int K) {
double low = 0;
int n = s.size();
double high = s[n - 1] - s[0];
while (high - low >= 1e-6) {
double mid = (low + high) / 2.0;
int x = ok(mid, s);
if (x > K) {
low = mid;
}
else {
high = mid;
}
}
return high;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3,4,5,6,7,8,9,10};
cout << (ob.minmaxGasDist(v, 9));
}输入值
{1,2,3,4,5,6,7,8,9,10}, 9输出结果
0.5