【NOIP 2015 提高组】跳石头（洛谷题面）

题目

题目描述：

一年一度的“跳石头”比赛又要开始了！

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 NN 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 MM 块岩石（不能移走起点和终点的岩石）。

输入格式：

第一行包含三个整数 L,N,ML,N,M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 L≥1L \geq 1 且 N≥M≥0N \geq M \geq 0。

接下来 NN 行，每行一个整数，第 ii 行的整数 Di (0<Di<L)D_i\,( 0 < D_i < L)， 表示第 ii 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

输出格式：

一个整数，即最短跳跃距离的最大值。

数据范围与说明：

输入输出样例 1 说明

将与起点距离为 22 和 1414 的两个岩石移走后，最短的跳跃距离为 44（从与起点距离 1717 的岩石跳到距离 2121 的岩石，或者从距离 2121 的岩石跳到终点）。

数据规模与约定

对于 20%20\%的数据，0≤M≤N≤100 \le M \le N \le 10。
对于 50%50\% 的数据，0≤M≤N≤1000 \le M \le N \le 100。
对于 100%100\% 的数据，0≤M≤N≤50000,1≤L≤1090 \le M \le N \le 50000,1 \le L \le 10^9。

输入输出样例 #1

输入：

1
2
3
4
5
6
25 5 2 
2
11
14
17 
21

输出：

1
4

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;
int l,n,m,a[50006],ans;
bool check(int mid){
    int cnt=0,j=0;
    for(int i=1;i<=n+1;i++){
        if(a[i]-a[j]<mid){
            cnt++;
        }else{
            j=i;
        }
    }
    if(cnt>m){
        return false;
    }else{
        return true;
    }
}
int main(){
    scanf("%d %d %d",&l,&n,&m);
    for(int i=1;i<=n;i++)   scanf("%d",&a[i]);
    a[n+1]=l;
    int left=0,right=l;
    while(left<=right)
     {
         int mid=left+(right-left)/2;
         if(check(mid)){
              left=mid+1;
              ans=mid;
          }
        else right=mid-1;
     }
    cout<<ans<<endl;
    return 0;
}