题目链接

「一本通 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;
}

评论