C++で最小距離が最大になるように配列からポイントを選択します

この問題では、N個のインデックス位置を表すn個の要素の配列arr []が与えられ、C個の磁石があります。私たちの仕事は、これらすべての磁石を、最も近い2つの磁石間の距離ができるだけ大きくなるように印刷することです。

問題を理解するために例を見てみましょう

入力 −配列={1、4、6、12、28、44} C =4

出力 − 11

この問題を解決するために、最大距離まで二分探索を使用します。最大距離を固定してから、すべての磁石を0から最大距離の間に配置することが有効です。

次に、二分探索を適用して中間値を見つけ、磁石を配置できるかどうかを確認します。はいの場合は、磁石を配置し、中央を最大距離として扱い、同じ手順に従います。

例

ソリューションの実装を示すプログラム

#include <iostream>
using namespace std;
bool canPlace(int arr[], int n, int C, int mid){
   int magnet = 1, currPosition = arr[0];
   for (int i = 1; i < n; i++) {
      if (arr[i] - currPosition >= mid) {
         magnet++;
         currPosition = arr[i];
         if (magnet == C)
            return true;
      }
   }
   return false;
}
int minDistMax(int n, int C, int arr[]){
   int lo, hi, mid, ans;
   lo = 0;
   hi = arr[n - 1];
   ans = 0;
   while (lo <= hi) {
      mid = (lo + hi) / 2;
      if (!canPlace(arr, n, C, mid))
         hi = mid - 1;
      else {
         ans = max(ans, mid);
         lo = mid + 1;
      }
   }
   return ans;
}
int main(){
   int C = 4;
   int arr[] = { 1, 4, 6,12, 28, 44 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"Maximised Minimum distance is "<<minDistMax(n, C, arr);
   return 0;
}

出力

Maximised Minimum distance is 11