k तत्वों को इस प्रकार रखें कि न्यूनतम दूरी C++ में अधिकतम हो

इस समस्या में, हमें n बिंदुओं की एक सरणी दी गई है जो एक ही रेखा पर स्थित हैं। हमारा काम सरणी के k तत्वों को इस तरह रखना है कि उनके बीच की न्यूनतम दूरी अधिकतम हो।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट - सरणी ={}

आउटपुट -

इस समस्या को हल करने के लिए, हमें अधिकतम संभव न्यूनतम दूरी ज्ञात करनी होगी। इस तरह की समस्या के लिए पहले हमें दिए गए एरे को सॉर्ट करना होगा और फिर बाइनरी सर्च करना होगा जब तक कि हमें बीच में समाधान न मिल जाए।

उदाहरण

हमारे समाधान के कार्यान्वयन को दिखाने के लिए कार्यक्रम,

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

आउटपुट

The maximized minimum distance is : 4