सरणी से ऐसे अंक चुनें कि न्यूनतम दूरी 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<<"Maximised Minimum distance is "<<minDistMax(n, C, arr);
   return 0;
}

आउटपुट

Maximised Minimum distance is 11