Luogu p2678 stone jumping

https://www.luogu.com.cn/problem/P2678

[NOIP2015 Improvement group ] Rock jumping

Background

annual “ Rock jumping ” The game is about to start again !

Title Description

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 format

The first line 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 . Guarantee $L\ge 1$ And $N\ge M\ge 0$.

Next $N$ That's ok , One integer per row , The first $i$ The whole number of lines $D_i(0<D_i<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 format

An integer , That is, the maximum value of the shortest jump distance .

Examples #1

The sample input #1

25 5 2 
2
11
14
17 
21

Sample output #1

4

Tips

I/o sample 1 explain ： The distance from the starting point will be $2$ and $14$ After the removal of the two rocks , The shortest jump distance is $4$( Distance from the starting point $17$ The rock jumps to the distance $21$ The rock of , Or from distance $21$ The rock jumped to the end ).

another ： about $20\%$ The data of ,$0\le M\le N\le 10$.

about $50\%$ The data of ,$0\le M\le N\le 100$.

about $100\%$ The data of ,$0\le M\le N\le 50,000,1\le L\le 1,000,000,000$.

Here's a row for you N A stone , You can move M A stone , Make the distance between the smallest two stones as long as possible ,N,M≤50000.

Ideas

Binary search right boundary

Code 1

#include<iostream>
using namespace std;
const int N=50010;
int L,n,m;
int d[N];
 
bool check(int mid) {
    
	int cnt=0,last=0;// 
	for(int i=1;i<=n;i++) {
    
		if(d[i] - last < mid) cnt++;// Take the stone 
		else last=d[i];  //  Skip if you don't take it 
	}
	return cnt<=m;
}
 
int main()
{
    
	scanf("%d%d%d",&L,&n,&m);
	for(int i=1;i<=n;i++) {
    
		scanf("%d",&d[i]);	
	}	
	n++;    
	d[n] = L;// Store the end distance 
	int l = 1 ,r = 1000000000; //r Take the maximum value to ac
	while (l < r) {
     // Binary search right boundary   Because it's looking for   Maximum 
        int mid = (l + r + 1) /2;//check() The() function determines that the answer is in mid Left or right 
        if (check(mid))
            l = mid;
        else r = mid - 1;
    }
	printf("%d\n",r);// When r==l Jump out of the loop , Now find the answer , Output r or l Fine 
 	return 0;
}

Thank you for reading