题意

移走石头后，这个路线会有一个最短跳跃距离。排列组合让这个距离最大

思路

二分找答案（最大的最短跳跃距离），找到合格的答案。合格的答案需要 check()

check()

检测这个答案，将间距大于答案的石头移走，看看移走的石头和组委会移走的石头相不相符（少了或多了）

代码

#include <bits/stdc++.h>
using namespace std;
int a[50005],R,n,m;
bool check(int x){
	int cnt = 0,idx = 0;
	for (int i = 1;i <= n + 1;i++){	// 到 n + 1 结束是因为要算上终点的石头
		if (a[i] - a[idx] >= x)	idx = i;	// 如果 a[i] 到 a[idx] 的距离超过最短距离的最大值，就把它们中间的石头移走
		else cnt++;	// 否则移的石头加 1
	}
	return cnt <= m;	// 移的石头是否符合要求
}
int main(int argc, char **argv){
	cin >> R >> n >> m;	// 连起来读一遍（bushi）
	for (int i = 1;i <= n;i++){
		cin >> a[i];
	}
	a[n + 1] = R;	// 把终点的石头加进来
	int l = 1,r = R,mid = (l + r + 1) >> 1;
	while (l < r){
		mid = (l + r + 1) >> 1;
//		printf("%d %d %d\n",l,mid,r);
		if (check(mid))	l = mid;	// 移的石头符合要求，答案在右边（不是 mid+1 是因为如果 mid 的是答案会略过正确答案）
		else r = mid - 1;	// 同理在左边
//		printf("%d %d %d\n",l,mid,r);
	}
	cout << l;
	return 0;
}

$update 2024/7/9:$ 更新了无特判的代码

$update 2024/7/10:$ 重写了思路

题意

• 移走 $M$ 个石头,使得每两个石头最短的距离最长
• 输出最短的距离最长的长度
• "最短的距离最长" 解释: 移走 $M$ 个石头后每一种组合的一堆石头中两个石头间最短的距离是最长的

思路

• 用二分(当然的)
• 二分的值是:最短的距离最长的值
• 重点在 $check()$

$check()$ 的思路

• 设置两个变量,一个统计移的个数 $bs$ ,一个是前一个石头的位置 $id$
• $a[i]-a[id]$是求每两个石头的距离
• 注意要更新 $id$
• 如果每两个石头的距离不足时,需要统计到 $bs$

二分模拟

输入 :
25 5 2
2
11
14
17
21

过程(l,m,r) :
0 500000000 1000000000
0 249999999 499999999
...(详细在题解最下面)
0 475 951
0 237 474
0 118 236
0 58 117
0 28 57
0 13 27
0 6 12
0 2 5
3 4 5
5 5 5

输出 :
4

$check()$ 模拟

样例:
1 2 5 12 18
m=5
bs=0
id=0

过程:

i=1:
'.' 2-1<m
.'. bs=1,id=0

i=2:
'.' 5-1<m
.'. bs=2,id=0

i=3:
'.' 12-1≥m
.'. bs=2,id=3

i=4:
'.' 18-12≥m
.'. bs=2,id=4

.'. check() 返回 bs≤M 为 1 
.'. l 会左缩区间

无特判$hack$数据的AC代码

#include<iostream>
#define int long long
using namespace std;
int L,n,M;
int a[114514];
int l=0,m=500000000,r=1000000000;
bool check()
{
	int bs=0,id=0;//一个统计移的个数,一个是前一个石头的位置
	for(int i=1;i<n;i++)//从1开始
	{
		if(a[i]-a[id]>=m)//距离
		{
			id=i;//更新
		}
		else
		{
			bs++;//移走
		}
	}
	return bs<=M;//注意返回的是什么
}
signed main()
{
	cin>>L>>n>>M;//输入
	a[0]=0;//起点
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];//输入
	}
	a[n+1]=L;//终点
	n+=2;//算上起点与终点
	while(l<=r)//注意范围
	{
		m=(l+r)/2;//二分(中分头...)
		if(check())//移的少了
		{
			l=m+1;//左移
		}
		else
		{
			r=m-1;//右移
		}
	}
	cout<<l-1;//输出
	return 0;//完结散花
}

二分模拟省略的内容

0 500000000 1000000000
0 249999999 499999999
0 124999999 249999998
0 62499999 124999998
0 31249999 62499998
0 15624999 31249998
0 7812499 15624998
0 3906249 7812498
0 1953124 3906248
0 976561 1953123
0 488280 976560
0 244139 488279
0 122069 244138
0 61034 122068
0 30516 61033
0 15257 30515
0 7628 15256
0 3813 7627
0 1906 3812
0 952 1905
0 475 951
0 237 474
0 118 236
0 58 117
0 28 57
0 13 27
0 6 12
0 2 5
3 4 5
5 5 5