Lời giải: Hàng rào bảo vệ

Ý tưởng

Sắp xếp các vị trí tăng dần. Đặt camera đầu tiên để nó phủ được tọa độ nhỏ nhất \(p_1\): camera đặt ở \(\text{pos}\) sao cho \(\text{pos} - R \le p_1 \le \text{pos} + R\). Để phủ được nhiều nhất về phía phải (bao nhiêu điểm nhất có thể), đặt \(\text{pos} = p_1 + R\).

Sau khi camera hiện tại phủ xong đến \(\text{right} = p_1 + 2R\), mọi điểm \(p_i \le \text{right}\) đều đã phủ. Điểm đầu tiên \(p_j > \text{right}\) cần camera mới: đặt tại \(p_j\), phủ đến \(p_j + 2R\). Tiếp tục.

Với \(R\) cho trước, đếm số camera cần dùng: \(f(R) = 1 + $ số điểm $p_i\) sao cho \(p_i > p_{prev} + 2R\). \(f\) là đơn điệu giảm theo \(R\) (càng \(R\) lớn càng ít camera).

Thuật toán

• Cận dưới: \(0\) (nếu \(K \ge N\) mọi điểm có thể đặt camera riêng).
• Cận trên: \(\max p_i - \min p_i\) (bao trùm cả đoạn).
• Thử \(R\): nếu \(f(R) \le K\) thì \(hi = R\); ngược lại \(lo = R + 1\).

Độ phức tạp

• Thời gian: \(O(N \log(\max p_i))\).
• Bộ nhớ: \(O(N)\).

Mã nguồn tham khảo

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, K;
    cin >> N >> K;
    vector<long long> p(N);
    for (int i = 0; i < N; i++) cin >> p[i];
    sort(p.begin(), p.end());

    auto can = [&](long long R) -> bool {
        int used = 1;
        long long last = p[0];
        for (int i = 1; i < N; i++) {
            if (p[i] - last > 2 * R) { used++; last = p[i]; }
        }
        return used <= K;
    };

    long long lo = 0, hi = p.back() - p.front();
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (can(mid)) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << "\n";
    return 0;
}