在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