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

इस समस्या में, हमें एक ही रेखा पर स्थित 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 << "अधिकतम न्यूनतम दूरी है : " << maxMinDist(arr, n, k);
    return 0;
}

आउटपुट

अधिकतम न्यूनतम दूरी है : 4