অ্যারে থেকে পয়েন্ট বাছাই করুন যাতে ন্যূনতম দূরত্ব C++ এ সর্বাধিক করা হয়

এই সমস্যায়, আমাদেরকে n উপাদানগুলির একটি অ্যারে অ্যারে দেওয়া হয়েছে যা 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