এই সমস্যায়, আমাদেরকে 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
