详见这篇题解

详见这篇题解

题意

• 移走 $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