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 << "अधिकतम न्यूनतम दूरी है " << minDistMax(n, C, arr);
    return 0;
}

आउटपुट

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