数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 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
更新于: 2020-04-17
171 次浏览
广告