从数组中选取点，以使最小距离在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