题目描述
在运动会上，小明从数轴的原点开始向正方向立定跳远。项目设置了 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。

大致讲一下本体的思路：自己可以增加的m可以看成是断点，在将所有的m加上去之后保证跳跃距离相对平均，那么便是把在未加断点的一些较大的跳跃距离进行拆分成多个小距离来保证。（采用二分法）而题目中所说的一次爆发使跳跃距离可以增加一倍，就相当于额外获得了一个断点。

#include<iostream>
using namespace std;
int n, m;
int arr[1000000] = { 0 };//这个地方数组要开大一点，不然会有段错误的问题
//判断mid是否为可以完成这个项目的L
bool judge(int mid) {
	int count = m+1;
	for (int i = 1; i < n; i++) {
		int k = arr[i] - arr[i - 1];//k为相邻检查点之间的距离，只有当k比每次跳跃的距离mid大时，才需要设置m这个断点。每设置一个断点会使count-1.
		if (k > mid) {
		//此处未考虑到一种情况，比如跳跃间隔为k12，mid为4，12/4=3，但实际上只需要设置两个断点，故导致测试点未全部通过。
			count -= k / mid;
			if (count < 0) return false;
		}
		
	}
	return true;
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	//这里设置min为可以完成这个项目的最小值L，
	//max为可以完成这个项目的最大值L
	int min = 1, max = 105 * 108 + 1;
	int mid;
	//采用二分法进行寻找可以完成这个项目范围内的L，逐步缩小L的范围
	while (min < max) {
		mid = (min + max) / 2;
		if(judge(mid)) max = mid;
		else min = mid + 1;
	}
	cout << max;
	return 0;
}

以上为第一次代码，但因为未考虑m点设置的全部问题，故导致第二个测试点通不过，其他测试点全过，以下为修改过的完整代码。

#include<iostream>
using namespace std;
int n, m;
int arr[1000000] = { 0 };
bool judge(int mid) {
	int count = m+1;
	for (int i = 1; i < n; i++) {
		int k = arr[i] - arr[i - 1];
		if (k > mid) {
			if (k % mid != 0) {
				count -= k / mid;
				if (count < 0) return false;
			}
			else {
				count -= (k / mid - 1);
				if (count < 0) return false;
			}
		}
		
	}
	return true;
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	int min = 1, max = 105 * 108 + 1;
	int mid;
	while (min < max) {
		mid = (min + max) / 2;
		if(judge(mid)) max = mid;
		else min = mid + 1;
	}
	cout << max;
	return 0;
}