153 lines
5.1 KiB
Markdown
153 lines
5.1 KiB
Markdown
# 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;
|
||
}
|
||
|
||
|
||
``` |