碎碎念
伤心啊！2022年比赛时，一道题没想明白用二分能解决，错失了AC机会，
今年我一定要在二分上下功夫，不能老在一个坑跌倒啊！
题目：[NOIP2015 提高组] 跳石头
题目原文请移步下面的链接
- https://www.luogu.com.cn/problem/P2678
- 参考题解：https://www.luogu.com.cn/problem/solution/P2678
- 标签：
贪心、二分 - 难度：
普及/提高-
题解
思路
- 最初以为是差分思路，而差分后其实是个波动数列，做不了二分，后来看了题解大致捋一下
- 整体框架是以一般性二分为基础，中间处理过程，首先判断当前的mid是否符合要求
- 如果符合就往右半区找有没有更大的符合要求的答案
- 如果当前mid已经不符合，证明这是个错解，应该往左半区找答案
- 当左右半区重合时，退出程序并输出即可
代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
#define endl 'n';
void best_coder() {
int n, m, l;
scanf("%d%d%d", &l, &n, &m);
vector<int> v(n 2);
for (int i = 1; i <= n; i) {
scanf("%d", &v[i]);
}
v[n 1] = l;
int x = 1, y = l;
int mid;
int ans;
while (x <= y) {
int cnt = 0;
int now = 0;
mid = (x y) >> 1;
for (int i = 1; i <= n 1; i) {
if (v[i] - v[now] < mid) {
cnt;
} else {
now = i;
}
}
if (cnt <= m) {
x = mid 1;
ans = mid;
} else {
y = mid - 1;
}
}
printf("%d", ans);
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
// 返回
return 0;
}
END
