从数组中选取点，以使最小距离在C ++中最大化

在这个问题中，我们得到了n个元素的数组arr []，它们代表N个索引位置，并且有C个磁铁。我们的任务是打印所有这些磁体，以使两个最近的磁体之间的距离尽可能大。

让我们举个例子来了解这个问题，

输入-数组= {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