Lời giải: Bò trong chuồng

Ý tưởng

Sắp xếp vị trí các chuồng tăng dần. Đặt con bò đầu tiên vào chuồng trái nhất. Với mỗi con bò tiếp theo, đặt vào chuồng trái nhất mà có khoảng cách \(\ge d\). Nếu đặt được \(\ge K\) con bò thì khoảng cách \(d\) khả thi.

Hàm kiểm tra \(f(d) = $ "có thể xếp $K\) con bò với khoảng cách \(\ge d\) hay không" có tính đơn điệu: nếu \(d\) khả thi thì mọi \(d' \le d\) cũng khả thi. Ta tìm \(d\) lớn nhất khả thi.

Thuật toán

• Cận dưới: \(1\).
• Cận trên: \(a_N - a_1\) (khoảng giữa hai chuồng xa nhau nhất).
• Lặp: \(mid = \lfloor (lo + hi + 1)/2 \rfloor\).
  • Nếu \(f(mid)\) đúng: tăng \(lo = mid\).
  • Ngược lại: giảm \(hi = mid - 1\).

Độ phức tạp

• Mỗi lần kiểm tra: \(O(N)\).
• Tổng: \(O(N \log(\max a_i))\).

Lưu ý

Vì ta tìm lớn nhất, cần dùng công thức mid = lo + (hi - lo + 1) / 2 để tránh lặp vô hạn khi \(hi = lo + 1\).

Mã nguồn tham khảo

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

bool check(const vector<long long>& a, int K, long long D) {
    int cnt = 1;
    long long last = a[0];
    for (size_t i = 1; i < a.size(); i++) {
        if (a[i] - last >= D) { cnt++; last = a[i]; }
    }
    return cnt >= K;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, K;
    cin >> N >> K;
    vector<long long> a(N);
    for (int i = 0; i < N; i++) cin >> a[i];
    sort(a.begin(), a.end());
    long long lo = 1, hi = a.back() - a.front();
    while (lo < hi) {
        long long mid = lo + (hi - lo + 1) / 2;
        if (check(a, K, mid)) lo = mid;
        else hi = mid - 1;
    }
    cout << lo << "\n";
    return 0;
}