P4768 饲养斗牛（基础）

解题思路

农夫约翰有 n 间牛舍，位置分别是 x1、x2……xn，他要放 m 头斗牛进去。斗牛脾气暴躁，离得太近会打架，所以约翰希望让"任意两头牛之间的最小距离"尽可能大，求这个最大的最小距离。这就是经典的"最大化最小距离"问题，用二分答案解决，分几步：

1. 第一步，先把牛舍位置排好队。 输入时牛舍位置并不是排好序的，所以第一步必须先把它们从小到大排序，这样扫描的时候才能按顺序判断两头牛之间距离够不够。

2. 第二步，想清楚怎么检查一个候选距离。 假设候选距离是 mid，要判断能不能放下 m 头牛、且任意两头牛距离都 ≥ mid。方法是贪心：第一头牛一定放在最左边（位置 stalls[1]）的牛舍；然后往后扫描，只要当前牛舍位置和"上一头牛的位置"之差 ≥ mid，就放下一头牛，并更新上一头牛的位置。这样一直放下去，数一数一共放了几头牛。

3. 第三步，明白贪心为什么对，并确定二分方向。 "每头牛都尽量放得靠左"，才能给后面的牛留下最多的空间，这是最有利于放下更多牛的放法，所以贪心是正确的。检查完：如果放的数量 ≥ m，说明 mid 可行，可以尝试更大的距离；如果放不下 m 头，说明 mid 太大，需要缩小。这里也有单调性：要求的距离越大，能放下的牛就越少；距离越小，能放下的牛就越多，所以二分完全适用。二分的范围是 1 到 stalls[n]-stalls[1]（最远两头牛的距离），answer 记录最大的可行距离。

4. 第四步，用样例验证。 5 间牛舍位置 1 2 8 4 9，排序后是 1 2 4 8 9，要放 3 头牛。检查距离 3：第 1 头放 1，第 2 头放 4（4-1=3），第 3 头放 8（8-4=4），能放下；检查距离 4：第 1 头放 1，下一头只能放 8（8-1=7），再往后 9-8=1 不够，只放下 2 头。所以最大最小距离是 3，和样例一致。

5. 第五步，看看两个边界。 如果只放 2 头牛，最好的答案一定是排好序后最远两个牛舍的距离，二分也会算出来；如果 m 比牛舍数还多，题目保证不会出现这种情况，但就算出现，贪心检查也自然会判断放不下。

参考代码

// 饲养斗牛：把m头牛放进n个牛舍，二分答案求最大的最小距离
#include <iostream>
#include <algorithm>
int main() {
    int n, m;
    std::cin >> n >> m;
    long long stalls[100005] = {0}; // stalls[i] 存第 i 个牛舍的位置
    for (int i = 1; i <= n; ++i) std::cin >> stalls[i];
    std::sort(stalls + 1, stalls + n + 1); // 先把牛舍位置从小到大排序
    long long low = 1, high = stalls[n] - stalls[1], answer = 0;
    while (low <= high) {
        long long mid = (low + high) / 2; // 假设任意两头牛之间距离至少是 mid
        int cnt = 1;              // 第一头牛放在最左边的牛舍
        long long last = stalls[1];
        for (int i = 2; i <= n; ++i) {
            if (stalls[i] - last >= mid) { // 与上一头牛的距离不小于 mid 才能放
                ++cnt;
                last = stalls[i];
            }
        }
        if (cnt >= m) { // 能放下 m 头牛，可以试试更大的距离
            answer = mid;
            low = mid + 1;
        } else {        // 放不下，说明距离太大，需要缩小
            high = mid - 1;
        }
    }
    std::cout << answer << '\n';
    return 0;
}

复杂度分析

排序要 O(n log n) 时间；二分答案的范围是 [1, stalls[n]-stalls[1]]，距离最大 1000000000，log2 约 30 次，每次判断要 O(n) 扫描一遍牛舍，所以总时间复杂度是 O(n log n + n log(距离))，n 最大 100000，约几百万次操作，非常快。空间复杂度 O(n)。这道题"二分距离 + 贪心检查"的组合是竞赛中的常见套路，值得记住。