NYOJ 586 - 瘋牛：二分答案 + 貪心檢查（Aggressive Cows 變體）

問題

N 個牛棚位置 x[i]，放 C 頭牛，最大化任意兩牛最小距離。N ≤ 100,000。

解法：二分距離 + 貪心放牛

• 排序牛棚位置
• 二分答案 d ∈ [0, maxPos-minPos]
• check(d)：從最左棚開始，每次選距離上一頭牛 ≥ d 的最左棚，能放 ≥ C 頭則可行

代碼

bool check(int d) {
    int cnt = 1, last = pos[0];
    for (int i = 1; i < n; ++i)
        if (pos[i] - last >= d) {
            if (++cnt >= c) return true;
            last = pos[i];
        }
    return false;
}
int solve() {
    int lo = 0, hi = pos[n-1] - pos[0];
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (check(mid)) lo = mid + 1;
        else hi = mid - 1;
    }
    return hi;  // 循環結束 hi 為最大可行值
}

注意

• 二分邊界收斂用 while (lo <= hi) + return hi 亦可，關鍵是 check 正確
• 時間 O(N log N + N log MaxDist)