[noip2015] jumping stone

subject ： [NOIP2015] Rock jumping , ha-ha , Let's look at a question with two answers today , This is from NOIP A question on , Okay , Let's have a look at the meaning of the title ：

The title description is copied , There may be some display errors , I'll put the title link below ！
Topic link ： [NOIP2015] Rock jumping

Title Description

annual “ Rock jumping ” The game is about to start again ！ The competition will be held in a straight river , There are some huge rocks in the river . The organizing committee has selected two rocks as the starting and ending points of the competition . Between the beginning and the end , Yes N A rock （ Rock without start and end ）. In the course of the game , The players will start from the starting point , Each step jumps to the adjacent rock , Until we reach the end . In order to improve the difficulty of the competition , The organizing committee plans to remove some rocks , Make the shortest jumping distance of players in the competition as long as possible . Due to budget constraints , At most, the organizing committee will move from the starting point to the end point M A rock （ You can't remove the rocks at the beginning and the end ）.

Input description

The first line of the input file contains three integers L,N,M, The distance from the starting point to the ending point , The number of rocks between the beginning and the end , And the maximum number of rocks removed by the Organizing Committee .
Next N That's ok , One integer per row , The first i The whole number of lines Di（0 < Di < L） It means the first one i The distance between the rock and the starting point . These rocks are given in the order of small to large distance from the starting point , And there won't be two rocks in the same place .

Output description

The output file contains only one integer , That is, the maximum value of the shortest jump distance .

Example 1

Input

25 5 2
2
11
14
17
21

Output

4

Ideas :

This question can be done in the way of two-point answer ！ Specifically, let's look directly at the code , Annotated amount ！

Let's look at success AC The code of ：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int l,n,m;
int a[100010];
int check(int x){
    
    int t=0;//t Indicates the position of the last stone 
    int cnt=0;// Record the number of stones that have been removed 
    for(int i=1;i<=n+1;i++){
    
        if(a[i]-t<x){
    // Need to move this stone  
            if(++cnt>m) return 0;// If the number of stones to be removed is greater than m, Then the scheme is not feasible 
        }else t=a[i];
    }
    return 1;
}
int main(){
    
    ios::sync_with_stdio(false);
    cin>>l>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    a[n+1]=l;
    int l1=0,r1=l;
    while(l1<r1){
    
         int mid=(l1+r1+1)>>1;
         if(check(mid)) l1=mid;
         else r1=mid-1;
    }
    cout<<l1;

    return 0;
}

Thanks for reading , Because the author level is limited , There are inevitably shortcomings , If the reader finds a problem , Please criticize , Leave a message in the message area or send a private message to inform , I will revise it as soon as possible . If you guys have any good solutions , Or meaningful solutions can be displayed in the comment area , Thank you very much .
Writing is not easy to , I hope all bosses will praise me , Add a focus on !