Đây là bài toán kinh điển về tìm kiếm nhị phân trên không gian kết quả. Ta muốn tìm khoảng cách tối thiểu \(D\) lớn nhất giữa hai con bò bất kỳ.

Hàm kiểm tra \(P(D)\): "Có thể bố trí \(C\) con bò vào các chuồng sao cho khoảng cách giữa hai con bò bất kỳ \(\ge D\) không?"

• Đầu tiên, ta sắp xếp tọa độ các chuồng bò tăng dần.
• Hàm kiểm tra \(P(D)\) được thực hiện bằng cách duyệt tham lam:
  • Đặt con bò thứ nhất tại chuồng đầu tiên (\(X_0\)).
  • Duyệt qua các chuồng tiếp theo, nếu tìm được một chuồng có tọa độ cách chuồng chứa con bò gần nhất ít nhất \(D\), ta đặt con bò tiếp theo tại đây.
  • Nếu đặt đủ \(C\) con bò thì trả về true, ngược lại trả về false.

Áp dụng Tìm kiếm nhị phân cho khoảng cách \(D\) trong đoạn \([1, X_{N-1} - X_0]\):

• Nếu \(P(mid) = true\): khoảng cách \(mid\) khả thi, ta thử tăng khoảng cách lên (lo = mid + 1).
• Nếu \(P(mid) = false\): khoảng cách \(mid\) quá lớn, ta giảm khoảng cách xuống (hi = mid - 1).

Độ phức tạp: \(O(N \log N + N \log(\max(X)))\).

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool canPlace(const vector<long long>& x, int c, long long d) {
    int count = 1;
    long long last_pos = x[0];
    for (size_t i = 1; i < x.size(); ++i) {
        if (x[i] - last_pos >= d) {
            count++;
            last_pos = x[i];
            if (count >= c) return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, c;
    if (!(cin >> n >> c)) return 0;
    vector<long long> x(n);
    for (int i = 0; i < n; ++i) cin >> x[i];

    sort(x.begin(), x.end());

    long long lo = 1, hi = x[n - 1] - x[0];
    long long ans = 1;
    while (lo <= hi) {
        long long mid = lo + (hi - lo) / 2;
        if (canPlace(x, c, mid)) {
            ans = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    cout << ans << "\n";
    return 0;
}