自动搬运

查看原文

来自洛谷，原作者为

	seek_my_calling **

搬运于2025-08-24 21:42:20，当前版本为作者最后更新于2018-07-05 14:28:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

河中跳房子（经典二分答案）

• 呃呃呃我是第一次写题解，请大佬指教。
• 这题是经典的二分答案题，求最大化的最小值。我们可以枚举最大跳远距离。大家千万别忘了把重点算进去！！当石头间的距离小于枚举出的距离时，记成答案。
• 好，不多说了，来看代码！！！

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int l,n,m,a[50003],ans;//定义变量
int count(int mid)
{
	int j=0,x=0;//x记录删去石头数
	for(int i=1;i<=n+1;i++)
	{
		if(a[i]-a[j] < mid)//石头间距离如果小于枚举的，就记录并删去。
        x++;
		else j=i;//否则移动起点。
	}
	return x;
}
int main()
{
	scanf("%d%d%d",&l,&n,&m);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	sort(a+1,a+1+n); //别忘了排序。
	a[n+1]=l;//记录终点
	int left=1,right=l;
	while(left<=right)//开始二分。
	{
		int middle=(left+right)/2;
		if(count(middle)<=m)//计数函数
        {
		ans=middle;
		left=middle+1;	
		} 
		else right=middle-1;
	}
	printf("%d",ans);//输出
	return 0;
}