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

题目描述

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

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

输出 #1

说明/提示

【样例解析】把牛放在 $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. 程序员的“偷懒”思维

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

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

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

第一步： 看到“最大化最小间距”，心里默念：“二分答案预警”。
第二步： 确定答案范围（比如到）。
第三步： 写一个 check 函数。这一步通常用贪心。

贪心逻辑： 既然要间距大，我就把第一头牛放在最左边，后面每一头牛都紧贴着“当前位置 + 间距”能放下的第一个点放。

第四步： 套二分模板。

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

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

#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;
}

5.1 KiB Raw Permalink Blame History Unescape Escape