Ý tưởng

• Chặt nhị phân lực đập ~R~ cần tìm.
• Với mỗi lực đập ~R~, kiểm tra xem có tồn tại cách đào thỏa mãn.

Đáp án sẽ là ~R~ nhỏ nhất sao cho tồn tại cách đào được ~N~ thỏi vàng.

Code tham khảo

const int N = 5e4 + 1;

int n, k, a[N];

bool check(int limit) {

    int cnt = 1, last = a[1];
    for(int i = 2; i <= n; ++i) {
        if (a[i] - last > 2 * limit + 1) {
            ++cnt;
            last = a[i];
        }
        if (cnt > k) return false;
    }

    return true;
}

void solve() {
    cin >> n >> k;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + 1 + n);
    int l = 0, r = 1e9, res = r + 1;
    while(l <= r) {
        int mid = (r - l) / 2 + l;
        if (check(mid)) {
            r = mid - 1;
            res = mid;
        } else l = mid + 1;
    }
    cout << res;
}