立定跳远-二分
问题描述
在运动会上，小明从数轴的原点开始向正方向立定跳远。项目设置了 n 个检查点 a1,a2,...,an 且 ai≥ai−1>0。小明必须先后跳跃到每个检查点上且只能跳跃到检查点上。同时，小明可以自行再增加 m 个检查点让自己跳得更轻松。在运动会前，小明制定训练计划让自己单次跳跃的最远距离达到 L，并且学会一个爆发技能可以在运动会时使用一次，使用时可以在该次跳跃时的最远距离变为 2L。小明想知道，L 的最小值是多少可以完成这个项目？
输入格式
输入共 2 行。第一行为两个正整数 n,m。第二行为 n 个由空格分开的正整数 a1,a2,...,an。
输出格式
输出共 1 行，一个整数表示答案。
样例输入
5 3
1 3 5 16 21
样例输出
3
样例说明
增加检查点 10,13,19，因此每次跳跃距离为 2,2,5,3,3,3,2，在第三次跳跃时使用技能即可。
评测用例规模与约定
对于 20% 的评测用例，保证 n≤102,m≤103,ai≤103。 对于100% 的评测用例，保证 2≤n≤105,m≤108,0<ai≤108。
运行限制
| 语言 | 最大运行时间 | 最大运行内存 |
|---|---|---|
| C++ | 1s | 256M |
| C | 1s | 256M |
| Java | 2s | 256M |
| Python3 | 3s | 256M |
| PyPy3 | 3s | 256M |
| Go | 3s | 256M |
| JavaScript | 3s | 256M |
解析：
通过题目看出，有一次最远距离变为2L，相当于加了一个检查点。二分法搜索答案。
代码：
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const ll MAX = 1e5 + 4;
const ll INF = 1e9;
ll a[MAX];
bool check(ll n, ll m,ll mid)
{for (int i = 1; i <= n; i++){ll l = a[i - 1], r = a[i];if (r - l <= mid)//可以直接跳过不需要插入检查点{continue;}else {while (r - l > mid)//当需要插入检查点时 判断要插入几个{if (m <= 0){return false;}l += mid;m--;}}}return true;
}
int main()
{ll n, m;cin >> n >> m;for (int i = 1; i <= n; i++){cin >> a[i];}ll l = 0, r = INF;while (l < r){ll mid = (l + r) / 2;if (check(n,m+1,mid))//增加一个检查点{r = mid;}else{l = mid + 1;}}cout << l;return 0;
}