【题解】USACO 愤怒的牛 | 洛灵酱的小窝

洛灵酱的小窝

闻道有先后，术业有专攻。

0%

【题解】USACO 愤怒的牛

发表于 更新于 分类于 Valine：

题目链接

「一本通 1.2 例 1」愤怒的牛

题目分析

所谓二分答案就是把所有的答案用二分的方法遍历一遍（前提是有序的单调序列），然后再用check()函数来判断答案的可行性。

求最小值最大或求最大值最小是典型的二分答案。

要注意的是二分的边界。

推荐阅读：二分查找怎么写，边界如何确定，我应该是要左边还是要右边，我为何如此的蠢？？？

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/* P10011 愤怒的牛
 * 来源: 信息学奥赛一本通 提高篇
 * 作者: RainbowBird
 * 日期: 2020-08-29
 * 算法: 二分答案
 */

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, m;
vector<int> a;

int check(int x) {
    int last = a[0]; // 先塞第一个牛棚
    int count = 1;
    
    // 遍历区间
    for (auto it = a.begin() + 1; it != a.end(); it++) {
        // 如果当前的牛棚和上一个牛棚的距离大于或等于最大值
        if (*it - last >= x) {
            last = *it;
            count++;
        }

        // 如果可以把牛全部放进牛棚
        if (count >= m) return true;
    }
    
    return false;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        a.push_back(x);
    }

    sort(a.begin(), a.end(), less<int>());

    // [l, r]为闭区间
    int l = a[0], r = a[n-1]; // l, r, mid都为距离
    while (l <= r) {
        int mid = (l + r) / 2; // mid为最短距离的最大值

        if (check(mid)) l = mid + 1;
        else r = mid - 1;
    }

    cout << r << endl;
    return 0;
}