C++でガソリンスタンドまでの最大距離を最小化する

水平方向の数直線が1本あるとします。その数直線上に、ステーション[0]、ステーション[1]、...、ステーション[N-1]の位置にガソリンスタンドがあります。ここで、N=ステーション配列のサイズです。ここで、隣接するガソリンスタンド間の最大距離であるDが最小になるように、K個のガソリンスタンドを追加します。 Dの可能な限り最小の値を見つける必要があります。

したがって、入力がステーション=[1、2、3、4、5、6、7、8、9、10]、K =9のような場合、出力は0.5

これを解決するには、次の手順に従います-

• 関数ok（）を定義します。これには、x、配列v、

  が必要です。

• ret：=0

• 初期化i：=0の場合、i

  • 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