B1910 【基础】愤怒的奶牛
大约 2 分钟
B1910 【基础】愤怒的奶牛
【算法】 二分答案、贪心
【C++】 二分、排序、贪心
【难度】 普及/提高−
一、题目简述
有 个隔间,坐标分别为 (无序)。要放入 头奶牛,每头牛占一个隔间。求一种放置方案,使得最近的两头牛之间的距离尽可能大。输出这个最大化的最近距离。
数据范围:,,。
二、解题思路
1. 问题类型
这是一个典型的最大化最小值问题:在所有满足"放得下 头牛"的方案中,让最近距离尽可能大。
2. 为什么能用二分
单调性:设最近距离为 。如果 能够放下 头牛,那么任何小于 的距离也能放下(间距要求更宽松)。如果 不行,更大的 更不行。
判定结果从"可行"变为"不可行",存在明确的转折点,满足二分条件。
3. check 函数设计(贪心)
check(d):贪心地尽可能把牛放得开一些。
- 将隔间按坐标排序
- 第一头牛放在
- 遍历后续隔间,如果当前隔间与上一头牛的距离 ≥ ,则放入一头牛,更新"上一头牛的位置"
- 最后统计放入的牛数是否 ≥
为什么贪心是对的:在已排序的隔间上,"尽量靠前放"不会使结果变差——越靠前放,留给后面的空间越大。
4. 手动模拟
隔间坐标 ,:
d = 3:
- 第1头放 1
- 下个 ≥ 1+3=4,放 4
- 下个 ≥ 4+3=7,放 8
- 共 3 头 ✅
d = 4:
- 第1头放 1
- 下个 ≥ 1+4=5,放 8
- 下个 ≥ 8+4=12,没有了
- 共 2 头 ❌
答案 = 3。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
long long x[N];
int n, c;
bool check(long long d) {
int cnt = 1;
long long last = x[1];
for (int i = 2; i <= n; i++) {
if (x[i] - last >= d) {
cnt++;
last = x[i];
}
}
return cnt >= c;
}
int main() {
cin >> n >> c;
for (int i = 1; i <= n; i++) cin >> x[i];
sort(x + 1, x + n + 1);
long long l = 1, r = x[n] - x[1], ans = 0;
while (l <= r) {
long long mid = (l + r) / 2;
if (check(mid)) { ans = mid; l = mid + 1; }
else r = mid - 1;
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:,其中 是坐标范围()。排序 ,二分 。通常排序是瓶颈。
- 空间复杂度:,存储坐标数组。
