[USACO05FEB] 进击的奶牛 Aggressive Cows G

题目解析

最大化最近的两头牛之间的距离: 最小最大->二分

这是一个经典的 「二分答案 + 贪心 Check」 的题目。

1 题目解析与单调性证明

题目核心：我们需要在 $n$ 个牛舍中选择 $m$ 个，使得这 $m$ 个牛舍中，相邻两个牛舍的最小距离值最大。

解题思路：直接去计算“最大的最小距离”很难，但如果我们反过来思考： “给出一个距离 $d$ ，能不能放下 $m$ 头牛，使得任意两头牛间距都 $\ge d$ ？” 这个问题很容易用贪心算法解决：

先把牛舍位置排序。
第一头牛放在第一个位置。
之后每头牛都放在离上一头牛距离 $\ge d$ 的最近位置。
看最终能不能放得下 $m$ 头牛。

因为答案具有单调性，我们可以对距离 $d$ 进行二分查找。

使用反证法证明单调性

命题：设 $P\left(d\right)$ 表示“最小距离为 $d$ 时，能否成功放入 $m$ 头牛”。若 $d$ 是一个合法的解（即 $P\left(d\right)$ 为真），那么任何小于 $d$ 的距离 $d^{′}$ ( $d^{′}<d$ ) 也一定合法。

反证法证明：

假设命题不成立。即：存在一个距离 $d$ 是合法的（ $P\left(d\right)$ 为真），但在 $d$ 之前存在一个更小的距离 $d^{′}$ ( $d^{′}<d$ ) 是不合法的（ $P\left(d^{′}\right)$ 为假）。
推导：
- 既然 $P\left(d\right)$ 为真，说明我们可以找到 $m$ 个位置 $x_{p1},x_{p2},\dots ,x_{pm}$ ，满足任意相邻两点 $x_{p\left(i+1\right)}-x_{pi}\ge d$ 。
- 已知 $d>d^{′}$ 。
- 根据不等式的传递性，如果 $A\ge d$ 且 $d>d^{′}$ ，那么必然有 $A>d^{′}$ 。
- 因此，这 $m$ 个位置同样满足 $x_{p\left(i+1\right)}-x_{pi}>d^{′}$ 。
矛盾：
- 推导结果表明，对于距离 $d^{′}$ ，我们也至少能找到一种方案（即 $d$ 对应的那个方案）放下 $m$ 头牛。
- 这说明 $P\left(d^{′}\right)$ 应该为真。
- 这与假设（ $P\left(d^{′}\right)$ 为假）相矛盾。
结论：
- 假设不成立。
- 原命题成立：如果距离 $d$ 可行，那么所有小于 $d$ 的距离都可行。

这意味着答案分布是这样的：[可行, 可行, ..., 可行, (最大值), 不可行, 不可行...]。这正是二分查找适用的场景。

2 代码实现

为了适配模板（bs_find 寻找第一个满足条件的位置），我们需要稍微转换一下思维：

你的模板中：当 check 为真时，执行 r = m（向左找）。
通常题目是求“可行”的最大值。
我们可以定义 check 函数为：“判断距离 $x$ 是否不可行（太大）”。
- 如果距离 $x$ 太大（不可行），返回 true。此时我们要找更小的，r = m，符合模板。
- 如果距离 $x$ 可行，返回 false。此时我们要找更大的，l = m + 1，符合模板。
最终 bs_find 返回的是第一个不可行的距离。
答案就是 bs_find(...) - 1。

代码

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2025-12-25 08:47:01
 */
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 2e5+5; // 数据范围是1e5，开稍微大一点
int n, m;
int a[maxn];

// 计算中间值
int mid(int l,int r) { return (l+r) >> 1; }

// check 函数逻辑：
// 我们尝试以 val 作为最小间距来放牛
// 如果 【不能】 放下 m 头牛，说明 val 太大了，返回 true (让二分往左走)
// 如果 【能】 放下 m 头牛，说明 val 合法（可能还有更大的），返回 false (让二分往右走)
bool check(int val){
    int cow_cnt = 1;       // 第一头牛肯定放在第一个位置
    int last_pos = a[1];   // 上一头牛的位置
    
    for(int i = 2; i <= n; i++) {
        // 如果当前隔间和上一头牛的距离 >= val，就可以放一头
        if(a[i] - last_pos >= val) {
            cow_cnt++;
            last_pos = a[i];
        }
    }
    
    // 如果放下的牛数量 < m，说明 val 这个距离太大了，这种方案【不满足】题目要求
    // 对应二分模板：我们需要找更小的距离，所以返回 true 让 r = m
    return cow_cnt < m;
}

// bs_find = binary search find
// 返回第一个满足条件(check返回true)的位置
// 在本题逻辑中，返回的是第一个【不可行/距离过大】的位置
int bs_find(int l,int r) {
    while( l < r) {
        int m = mid(l,r);
        if( check(m)) // 如果距离太大了(不可行)
            r = m;    // 尝试缩小距离，保留这个不可行的边界
        else          // 如果距离可行
            l = m+1;  // 尝试更大的距离
    }
    return l ;
}

void init(){
    // 读入数据
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    // 贪心策略的前提是位置有序，题目没保证有序，必须排序
    sort(a + 1, a + 1 + n);
}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    
    init();

    // 二分范围：
    // 最小距离可能是 0 (或者1)
    // 最大距离可能是 a[n] - a[1] (头尾差距)，为了作为哨兵，右边界设得稍大一点 1e9+1
    // bs_find 将返回第一个 "不可行" 的距离
    int ans_idx = bs_find(0, 1000000001);

    // 因为 ans_idx 是第一个不可行的，所以 ans_idx - 1 就是最后一个可行的（最大的最小距离）
    cout << ans_idx - 1 << endl;
    
    return 0;
}