# P1824 [USACO05FEB] 进击的奶牛 Aggressive Cows G

## 题目描述

农夫约翰建造了一座有 $n$ 间牛舍的小屋，牛舍排在一条直线上，第 $i$ 间牛舍在 $x_i$ 的位置，但是约翰的 $m$ 头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。

牛们并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。为了不让牛互相伤害。约翰决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是多少呢？

## 输入格式

第一行用空格分隔的两个整数 $n$ 和 $m$；

下面 $n$ 行为 $n$ 个用空格隔开的整数，表示位置 $x_i$。

## 输出格式

一行一个整数，表示最大的最小距离值。

## 输入输出样例 #1

### 输入 #1

```
5 3
1
2
8
4
9
```

### 输出 #1

```
3
```

## 说明/提示

【样例解析】把牛放在 $1$，$4$，$8$ 这三个位置，距离是 $3$。容易证明最小距离已经最大。

【数据范围】对于 $100\%$ 的数据，$2 \le n \le 10^5$，$0 \le x_i \le 10^9$，$2 \le m \le n$。不保证 $x$ 数组单调递增。


哈哈，这种反应太正常了！初次接触这种题，谁都会觉得这种“反着来”的思路简直是脑洞大开。

这种思维方式在算法竞赛里有一个专门的套路，叫 **“二分答案”**。其实它不是靠灵光一现，而是有迹可循的“职业习惯”。

我们可以把这种思维过程拆解为三个“直觉点”，以后你看到类似的题，也能秒懂。

---

### 1. 关键词暗示：看到“最大化最小值”

当你看到题目要求：

* **最大化** 某个 **最小值**
* 或者 **最小化** 某个 **最大值**

这在算法界几乎就是**明示**：请用二分搜索！

**为什么？** 因为直接计算“最优布局”非常困难，要考虑无数种组合。但如果我问你：“间距为  行不行？”你只需要从左往右摆摆看（贪心），一眼就能看出行不行。把“寻找题”变成“判断题”，难度瞬间降维。

### 2. 利用“单调性”：答案像个开关

这是最关键的直觉。你可以这样想：

* 如果间距是1  米，肯定能放下  头牛（太简单了）。
* 如果间距是1000000  米，肯定放不下（太远了）。
* 在这中间，一定存在一个**临界点**。在临界点左边，全是“行”；在临界点右边，全是“不行”。

既然有这种**单调性**（一半行，一半不行），我们就不需要一个个试，直接用**二分查找**去撞那个临界点。

### 3. 程序员的“偷懒”思维

正向思考（直接算位置）是“创造者思维”，很难；
反向思考（猜一个答案去验证）是“检查者思维”，很简单。

**计算机最擅长做简单的重复劳动。** 既然验证一次只需要 ，二分查找只需要  次，总共也就跑  次验证。与其想破脑袋去算最优解，不如直接“暴力”地猜几十次。

---

### 总结一下这个“坑”是怎么跳进去的：

1. **第一步：** 看到“最大化最小间距”，心里默念：“二分答案预警”。
2. **第二步：** 确定答案范围（比如  到 ）。
3. **第三步：** 写一个 `check` 函数。这一步通常用**贪心**。
* *贪心逻辑：* 既然要间距大，我就把第一头牛放在最左边，后面每一头牛都紧贴着“当前位置 + 间距”能放下的第一个点放。


4. **第四步：** 套二分模板。

> **这种感觉就像是：** 你去买衣服，不知道自己穿多大码。你不是拿尺子把自己全身量一遍再算缩水率（正向计算），而是直接拿 L 码试一下。大了？换 M。还大？换 S。这就是二分答案。

**你要不要试着写一下这个 `check` 函数的伪代码？我可以帮你看看逻辑对不对。**



``` cpp
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
//int ax[] = {1, 2, 4, 8, 9};

//按照分布，检查是否能够排列即可
/*
  1、读入arr, mid
  2、按照分布排列，找到离mid格最近的槽位插入
 */
int check(const vector<int>& arr, int mid){
    if(arr.empty()) return 0;
    
    int cnt = 1;
    int n = arr.size();
    int dist = 0;
    for(int i = 1; i < n; ++i){
        dist += arr[i] - arr[i - 1];
        if(dist >= mid){
            cnt++;
            dist = 0;
        }
    }
    return cnt;
}

int main(){
    int n = 5, c = 3;
    cin >> n >> c;
    vector<int> arr(n);
    for(int i = 0; i < n; i++){
        cin >> arr[i];
        //arr[i] = ax[i];
    }
    sort(arr.begin(), arr.end());
    int smin = 0, smax = arr.back() - arr.front();
    //range [smin, smax], do mid to this range
    int l = smin, r = smax;
    int ans = 0;
    while(l <= r){
        int mid = (l+r)/2;
        int cc = check(arr, mid);
        if (cc >= c) {
            ans = mid;
            l = mid + 1;
        } else r = mid - 1;
    }
    cout << ans << endl;
    return 0;
}


```