在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