NOIP2015D2T1跳石头-二分法与贪心算法的应用

### 描述
一年一度的“跳石头”比赛即将开始！这项赛事将在一条直线型的河流中进行，河流中散布着多个巨大的岩石。比赛的起点和终点已由组织方选定。在起点与终点之间，存在N个岩石（不包括起点和终点）。比赛中，选手将从起点出发，每步跳向相邻的岩石，直到到达终点。

为了增加比赛的挑战性，组织方计划移除部分岩石，以使选手在比赛中的最小跳跃距离最大化。然而，由于预算限制，组织方最多只能移除M个岩石（起点和终点的岩石不可移除）。

### 格式
#### 输入格式
输入的第一行包含三个整数L、N、M，分别表示起点到终点的距离、起点和终点之间的岩石数量，以及组织方最多能移除的岩石数量。接下来的N行，每行包含一个整数Di（0
#### 输出格式
输出仅包含一个整数，表示最小跳跃距离的最大值。

### 样例
#### 样例输入1
```
25 5 2
2
11
14
17
21
```
#### 样例输出1
```
4
```

### 限制
- 对于20%的数据，0 ≤ M ≤ N ≤ 10。
- 对于50%的数据，0 ≤ M ≤ N ≤ 100。
- 对于100%的数据，0 ≤ M ≤ N ≤ 50000，1 ≤ L ≤ 1000000000。

### 提示
对于给定的样例，如果移除与起点距离为2和14的两个岩石，那么最短的跳跃距离将是4（从与起点距离17的岩石跳到距离21的岩石，或从距离21的岩石跳到终点）。

### 来源
NOIP 2015 提高组 Day 2 第一题

### 解题思路
此问题可以通过二分查找法来解决。二分查找的范围是从0到L。在每次二分时，需要检查当前的中间值是否满足条件，即在移除不超过M个岩石的情况下，能否保证所有跳跃的距离都不小于当前的中间值。具体的实现细节可以在代码中查看。

### 参考代码
```cpp
#include
#include
#include
#include
#include
using namespace std;
template inline void read(T &x){
bool f = 0; int ch = getchar(); x = 0;
while(ch <'0' || ch > '9'){ if(ch == '-') f = 1; ch = getchar(); }
while(ch >= '0' && ch <= '9'){ x = (x <<1) + (x <<3) + ch - '0'; ch = getchar(); }
if(f) x = -x;
}

int l, n, m, a[50003], L, R, tmp;

inline bool check(int u) {
int cnt = 0;
for(int i = 0; i int q = i + 1;
while(a[q] - a[i] if(q == n && a[q] - a[i] if(cnt > m) return false;
i = q;
}
return true;
}

int main() {
read(l); read(n); read(m);
for(int i = 1; i <= n; ++i) read(a[i]);
R = l;
a[++n] = l;
while(L <= R) {
int mid = (L + R) >> 1;
if(check(mid)) L = mid + 1;
else R = mid - 1;
}
printf("%d", L - 1);
return 0;
}
```