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

এই সমস্যাতে, n উপাদানের একটি অ্যারে arr[] দেওয়া আছে যা N সংখ্যক إندেক্স পজিশন নির্দেশ করে এবং C সংখ্যক ম্যাগনেট আছে। আমাদের কাজ হলো এই ম্যাগনেটগুলো এমনভাবে রাখা যাতে দুটি আসল নিকটবর্তী ম্যাগনেটের মধ্যে দূরত্ব যতসম্ভব বড় হয়।

উদাহরণ:

ইনপুট - array = {1, 4, 6, 12, 28, 44}, C = 4

আউটপুট - 11

সমাধানের জন্য, আমরা বাইনারি সার্চ ব্যবহার করে সর্বাধিক দূরত্ব বের করব। আমরা একটি সর্বাধিক দূরত্ব ফিক্স করব এবং ০ থেকে সেই সর্বাধিক দূরত্ব পর্যন্ত ম্যাগনেট রাখা যাচ্ছে কিনা তা চেক করব।

তারপর বাইনারি সার্চ প্রয়োগ করে মিডল মান বের করব এবং ম্যাগনেট রাখা সম্ভব কিনা চেক করব। যদি সম্ভব হয়, তবে ম্যাগনেট রাখব এবং মিডকে সর্বাধিক দূরত্ব ধরে একই প্রক্রিয়া চলাব।

উদাহরণ

সমাধানের বাস্তবায়ন:

#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