Đặt k phần tử sao cho khoảng cách nhỏ nhất được tối đa hóa trong C ++

Trong bài toán này, chúng ta đưa ra một mảng gồm n điểm nằm trên cùng một đường thẳng. Nhiệm vụ của chúng ta là đặt k phần tử của mảng sao cho khoảng cách tối thiểu giữa chúng là lớn nhất.

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

Đầu vào - mảng ={}

Đầu ra -

Để giải quyết vấn đề này, chúng ta sẽ phải tìm khoảng cách lớn nhất có thể tối thiểu. Đối với một vấn đề như vậy trước tiên, chúng ta cần sắp xếp mảng đã cho và sau đó thực hiện tìm kiếm nhị phân cho đến khi chúng ta nhận được giải pháp ở giữa.

Ví dụ

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

#include <bits/stdc++.h>
using namespace std;
bool canGenerateResult(int mid, int arr[], int n, int k) {
   int pos = arr[0];
   int elements = 1;
   for (int i=1; i<n; i++){
      if (arr[i] - pos >= mid){
         pos = arr[i];
         elements++;
         if (elements == k)
         return true;
      }
   }
   return 0;
}
int maxMinDist(int arr[], int n, int k) {
   sort(arr,arr+n);
   int res = -1;
   int left = arr[0], right = arr[n-1];
   while (left < right){
      int mid = (left + right)/2;
      if (canGenerateResult(mid, arr, n, k)){
         res = max(res, mid);
         left = mid + 1;
      }
      else
         right = mid;
   }
   return res;
}
int main() {
   int arr[] = {3, 5, 6, 9, 1, 8};
   int n = sizeof(arr)/sizeof(arr[0]);
   int k = 3;
   cout<<"The maximized minimum distance is : "<<maxMinDist(arr, n, k);
   return 0;
}

Đầu ra

The maximized minimum distance is : 4