เลือกจุดจากอาร์เรย์เพื่อให้ระยะทางขั้นต่ำสูงสุดใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ของ n องค์ประกอบที่แทนตำแหน่งดัชนี N และมี C แม่เหล็ก งานของเราคือวางแม่เหล็กเหล่านี้ให้ระยะห่างระหว่างแม่เหล็กสองตัวที่ใกล้ที่สุดมากที่สุด

มาดูตัวอย่างเพื่อเข้าใจปัญหา:

Input - array = { 1, 4, 6, 12, 28, 44 } C = 4

Output - 11

เพื่อแก้ปัญหานี้ เราจะใช้ binary search เพื่อหาระยะทางสูงสุด เราจะกำหนดระยะทางสูงสุดแล้วตรวจสอบว่าการวางแม่เหล็กทั้งหมดระหว่าง 0 ถึงระยะทางสูงสุดเป็นไปได้หรือไม่

จากนั้นเราจะใช้ binary search เพื่อหาค่ากลางและตรวจสอบว่าการวางแม่เหล็กเป็นไปได้หรือไม่ หากใช่ ให้วางแม่เหล็กและถือ mid เป็นระยะทางสูงสุดและทำตามขั้นตอนเดียวกัน

ตัวอย่าง

โปรแกรมแสดงการนำโซลูชันของเราไปใช้งาน:

#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