Chọn các điểm từ mảng sao cho khoảng cách tối thiểu được tối đa hóa trong C ++

Trong bài toán này, chúng ta được đưa ra một mảng arr [] gồm n phần tử đại diện cho N vị trí chỉ số và có C nam châm. Nhiệm vụ của chúng tôi là in tất cả các nam châm này sao cho khoảng cách giữa hai nam châm gần nhất càng lớn càng tốt.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào - mảng ={1, 4, 6,12, 28, 44} C =4

Đầu ra - 11

Để giải quyết vấn đề này, chúng tôi sẽ sử dụng tìm kiếm nhị phân đến khoảng cách tối đa. Chúng tôi sẽ cố định một khoảng cách tối đa và sau đó đặt tất cả các nam châm trong khoảng từ 0 đến tối đa là hợp lệ.

Sau đó, chúng tôi sẽ áp dụng tìm kiếm nhị phân để tìm các giá trị trung bình và kiểm tra xem có thể đặt được từ khóa hay không. Nếu có, sau đó đặt nam châm và coi giữa là khoảng cách tối đa và thực hiện theo quy trình tương tự.

Ví dụ

Chương trình thể hiện việc triển khai giải pháp của chúng tôi,

#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;
}

Đầu ra

Maximised Minimum distance is 11