Chọn điểm từ mảng sao cho khoảng cách nhỏ nhất được tối đa hóa trong C++

Trong bài toán này, chúng ta được cho mảng arr[] gồm n phần tử đại diện cho N vị trí chỉ số và có C nam châm. Nhiệm vụ là đặt tất cả các nam châm này sao cho khoảng cách giữa hai nam châm gần nhau nhất là lớn nhất có thể.

Ví dụ minh họa:

Đầu vào - mảng = { 1, 4, 6, 12, 28, 44 } C = 4

Kết quả - 11

Để giải bài toán, chúng ta sẽ dùng tìm kiếm nhị phân (binary search) để tìm khoảng cách lớn nhất. Chúng ta cố định một khoảng cách tối đa và kiểm tra xem việc đặt tất cả nam châm trong khoảng 0 đến khoảng cách tối đa đó có hợp lệ hay không.

Sau đó áp dụng tìm kiếm nhị phân để tìm giá trị trung gian và kiểm tra xem việc đặt nam châm có khả thi. Nếu có, đặt nam châm và coi mid là khoảng cách tối đa, tiếp tục quy trình tương tự.

Chương trình minh họa

#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 << "Khoảng cách nhỏ nhất được tối đa hóa là " << minDistMax(n, C, arr); 
    return 0; 
}

Kết quả

Khoảng cách nhỏ nhất được tối đa hóa là 11