题解

题目类型：二分查找 + 贪心判断
核心算法：二分最大最小值问题（最大化最小间距）

一、题意概述

有一条长度为 L 的河流，在其上有 M 块石头，给出每块石头与河岸的距离。
现在允许移走其中 最多 N 块石头，要求使得剩下的所有相邻“可落脚点”（包含河岸）的最小间距尽可能大。

换句话说，就是要 移除不超过 N 块石头后，最大化相邻两点的最小距离。

二、思路分析

这类“最大化最小值”的问题非常典型，可以用 二分答案 + 贪心验证。

1. 二分查找的思想

假设我们猜一个答案 mid，即：

“最小间距至少为 mid” 是否可行？

如果可以做到，我们就尝试增大 mid；
如果做不到，就减小 mid。
最终得到的最大可行 mid 就是答案。

2. 可行性判断函数 work(std)

作用：判断最小间距 std 是否能满足。

方法：

• 从左到右扫描所有石头；
• 若当前石头与上一个“保留点”的距离 < std，说明间距太小，需要移除这块石头；
• 否则，这块石头可以保留，并更新“最近保留点”。
• 统计总共移除了多少块石头 cnt。
• 若 cnt > N，表示太多石头被移除，不可行；
• 否则表示可行。

代码中 tool 变量记录上一个保留石头的下标。

3. 特殊边界处理

代码中最后还有一段：

if(L - arr[M] < std && arr[M] - arr[M - 1] >= std) cnt++;

这句是为了检查终点到最后一块石头的距离是否满足要求。
如果最后一段太短但前面一段足够长，则尝试多移除一个石头补偿间距不足。

三、二分查找函数 binary(l, r)

对间距进行二分：

1. 初始区间 [1, L]；
2. 每次取中点 mid = (l + r) / 2；
3. 若 work(mid) 可行，说明可以尝试更大的最小间距（l = mid）；
4. 否则缩小（r = mid）；
5. 最后返回最大的可行 mid。

通过不断收缩区间找到答案。

四、整体流程总结

1. 输入：河长 L、石头数 M、可移除数 N；
2. 读入石头位置并排序（题中默认输入已按从小到大）；
3. 若 M == 0：直接输出 L；
4. 若 N == 0：不能移石头，最小间距即为相邻石头的最小距离；
5. 否则用 binary(1, L) 找出最大可行的最小间距并输出。

五、复杂度分析

• 每次判断 work() 需 O(M)；
• 二分范围约为 O(log L)；
• 总复杂度：O(M log L)；
• 空间复杂度：O(M)。

六、算法本质

该题是典型的 最大化最小值问题（Maximin）。
通过“二分答案 + 贪心判断”实现高效求解，
是一类非常常见的思维模式（与“跳石头”、“分配任务”等问题同型）。

七、代码实现

#include<stdio.h>
int arr[100000];
int L,M,N;
int work(int std){
	int cnt=0,tool=0;
	for(int i=1;i<=M;i++){
		if((arr[i]-arr[tool])<std){
			cnt++;
		}else{
			tool=i;
		}
	}
	if(L-arr[M]<std&&arr[M]-arr[M-1]>=std)cnt++;
	if(cnt>N)return 0;
	else return 1;
}
int binary(int l,int r){
	int mid=(l+r)/2;
	while(mid!=l){
		if(work(mid)){
			l=mid;
			mid=(l+r)/2;
		}else{
			r=mid;
			mid=(l+r)/2;
		}
	}
	if(work(mid+1))return mid+1;
	else return mid;
}
int main(){
	int min=1000000000;
	scanf("%d%d%d",&L,&M,&N);
	for(int i=1;i<=M;i++){
		scanf("%d",&arr[i]);
		if(min>arr[i]-arr[i-1])min=arr[i]-arr[i-1];
	}
	if(M==0){
		printf("%d\n",L);
	}else if(N==0){
		printf("%d\n",min);
	}else{
		printf("%d\n",binary(1,L));
	}
}