B1909 【提高】跳石头
大约 3 分钟
B1909 【提高】跳石头
【算法】 二分答案、贪心
【C++】 二分、贪心验证
【难度】 普及+/提高
一、题目简述
一条长度为 的笔直河道,起点为 ,终点为 。河道中有 块岩石,第 块距起点距离为 (严格递增)。选手从起点出发,依次跳到岩石上,最终到达终点。组委会至多可以移走 块岩石(不能移走起点和终点)。求移走岩石后,最短跳跃距离的最大值。
数据范围:,,。
二、解题思路
1. 问题本质
与"愤怒的奶牛"类似,都是最大化最小值问题,但这里的对象是"跳跃距离"而非"牛之间的距离"。
2. 为什么能用二分
单调性:设最短跳跃距离为 。如果 能通过移走至多 块石头实现,那么任何小于 的距离也能实现。如果 不行,更大的 也不行。
二分的转折点就是答案。
3. check 函数设计(贪心模拟)
check(d):模拟选手从起点开始跳跃,确保每一跳的距离 ≥ 。
last = 0(上一块保留石头距起点的距离,初始为起点 0)- 遍历每块石头 :
- 如果 ,说明这块石头太近,需要移走(
cnt++) - 否则,保留这块石头,更新
last = D_i
- 如果 ,说明这块石头太近,需要移走(
- 最后检查终点:如果 ,最后一段也不够,需要额外移走(但终点不能移,所以这段距离也必须满足 ≥ d)
- 若
cnt ≤ M,说明可行
4. 手动模拟
,石头位置 ,:
d = 5:
- 起点(0)→2: 2-0=2 < 5,移走石头2,cnt=1
- →11: 11-0=11 ≥ 5,保留,last=11
- →14: 14-11=3 < 5,移走石头14,cnt=2
- →17: 17-11=6 ≥ 5,保留,last=17
- →21: 21-17=4 < 5,移走石头21,cnt=3
- →25: 25-17=8 ≥ 5,保留
- cnt=3 > M=2 ❌
d = 4:
- 起点(0)→2: 2-0=2 < 4,移走石头2,cnt=1
- →11: 11-0=11 ≥ 4,保留,last=11
- →14: 14-11=3 < 4,移走石头14,cnt=2
- →17: 17-11=6 ≥ 4,保留,last=17
- →21: 21-17=4 ≥ 4,保留,last=21
- →25: 25-21=4 ≥ 4,保留
- cnt=2 ≤ M=2 ✅
答案 = 4。
5. 与"愤怒的奶牛"的对比
| 愤怒的奶牛 | 跳石头 | |
|---|---|---|
| 操作 | 放牛 | 移石头 |
| 贪心 | 尽量靠前放 | 不够就移走 |
| 检查 | 放得下 ≥ C 头 | 移走 ≤ M 块 |
| 终点 | 无特殊处理 | 最后一段也要检查 |
两道题本质都是二分 + 贪心的经典模板。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5;
int a[N];
int L, n, m;
bool check(int d) {
int cnt = 0, last = 0;
for (int i = 1; i <= n; i++) {
if (a[i] - last < d) cnt++;
else last = a[i];
}
if (L - last < d) cnt++; // 最后一段
return cnt <= m;
}
int main() {
cin >> L >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
int l = 1, r = L, ans = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) { ans = mid; l = mid + 1; }
else r = mid - 1;
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:。每次
check遍历 块石头 ,二分范围 ,约 30 次迭代。 - 空间复杂度:,存储石头位置数组。
