วาง k องค์ประกอบให้ระยะทางขั้นต่ำสูงสุดใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ของ n จุดที่อยู่บนเส้นตรงเดียวกัน งานของเราคือวาง k องค์ประกอบของอาร์เรย์ในลักษณะที่ระยะทางขั้นต่ำระหว่างพวกเขาถูกเพิ่มสูงสุด

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

Input - array = {}

Output -

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

ตัวอย่าง

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

#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