資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告