USACO备考冲刺必刷题 | P1676 Aggressive cows

学习C++从娃娃抓起！记录下USACO（美国信息学奥赛）备考学习过程中的题目，记录每一个瞬间。

附上汇总贴：USACO备考冲刺必刷题 | 汇总-CSDN博客

【题目描述】

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

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

【输入】

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

第二行为 n 个用空格隔开的整数，表示位置 xi。

【输出】

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

【输入样例】

5 3
1 2 8 4 9

【输出样例】

3

【代码详解】

#include <bits/stdc++.h>
using namespace std;
int n, m, l, r, mid;
int a[100005];
int main()
{
    cin >> n >> m;  // 输入n和m
    for (int i=1; i<=n; i++) {  // 输入n个牛舍的位置
        cin >> a[i];
    }
    sort(a+1, a+n+1);  // 按照从小到大排列，因为后面需要二分搜索
    l = a[1], r = a[n];  // 定义l和r
    while (l<r) {  // 二分模板
        int cnt=0;  // 统计可选择的牛舍
        mid = l + (r-l)/2;  // 二分模板
        int last = a[1];  // 定义待比较的牛舍，初始从第1个牛舍开始比较
        for (int i=2; i<=n; i++) {  // 往后遍历所有牛舍
            if (a[i]-last>=mid) {  // 如果两个牛舍之间的距离大于等于mid，即可以被选择
                cnt++;  // 统计数自增1
                last = a[i];  
            }
        } 
        // cout << "cnt " << cnt << endl;
        if (cnt<m-1) r = mid;
        else l = mid+1;
    }
    cout << l-1 << endl;  // 因为r先动，所以最终输出应该是l-1（l最后+1试探失败，所以需要l-1，即为mid）
    return 0;
}

【运行结果】

5 3
1 2 8 4 9
3