POJ 2456 / USACO Aggressive Cows：二分答案 + 貪心檢查

題目重述

N 個攤位 (N ≤ 100,000)，座標 x_i。放入 C 頭牛 (C ≤ N)，使**任意兩牛最小距離最大化**。輸出此最大最小距離。

核心演算法：二分搜尋答案 + 貪心驗證

1. 排序座標。
2. 二分搜尋距離 d (範圍 0 ~ max(x) - min(x))。
3. 驗證函式 canPlace(d)：貪心從第一個攤位放牛，之後每個攤位若距離上一頭牛 ≥ d 即放置。若能放 ≥ C 頭，回傳 true。

C++ 完整代碼

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

bool canPlace(const vector& pos, int C, int dist) {
    int count = 1;
    int last = pos[0];
    for (size_t i = 1; i < pos.size(); ++i) {
        if (pos[i] - last >= dist) {
            ++count;
            last = pos[i];
            if (count >= C) return true;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, C;
    while (cin >> N >> C) {
        vector pos(N);
        for (int i = 0; i < N; ++i) cin >> pos[i];
        sort(pos.begin(), pos.end());
        
        int lo = 0, hi = pos.back() - pos.front(), ans = 0;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (canPlace(pos, C, mid)) {
                ans = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

複雜度分析

• 排序：O(N log N)
• 二分搜尋：O(log MAX_DIST) ≈ O(log 1e9) ≈ 30 次
• 每次驗證：O(N)
• 總計：O(N log N + N log MAX_DIST) → 約 300 萬次操作，極快。

關鍵細節

• canPlace 必須從 **第一個攤位** 開始放 (貪心最優證明：盡早放置留更多空間給後續)。
• 二分邊界：lo=0 (最小距離可為 0)、hi=max-min。
• 輸入多組測資，while(cin>>N>>C) 處理至 EOF。

總結

Aggressive Cows 經典題：**排序 + 二分答案 + 貪心檢查**。二分距離，貪心驗證能否放入 C 頭牛，時間複雜度 O(N log MAX)，完美通過 N=100,000。