自动搬运

查看原文

来自洛谷，原作者为

	itandsoon 半缘修道半缘君

搬运于2025-08-24 21:53:24，当前版本为作者最后更新于2020-02-28 16:44:50，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

此题为二分求最优解的模板

对于任意一个给出的“空旷指数”G，我们应该怎样去判断它是否符合题目的意思呢？

我们可以想象，我们已知了这条路上的所有的路标，我们从头开始枚举两两相邻的路标的间距，如果大于G,那么已经不符合G为最大距离的条件了，为了使G满足,我们就可以在前一个路标前面G米处加一个路标，这样与前面一个就符合条件了，再判断新设的路标和后面的路标是否距离小于G,如果不，继续重复操作设置新路标

当新设的路标数已经超过题目所给最大增设值时，如果还有路标不满足G,但已经不能设置新路标了，所以该G值就不满足条件。相反，则G成立。

注意到，如果一个“空旷指数”成立，那么可能存在比它更小的解，但如果一个“空旷指数”不成立，那么答案只能比该值更大

确定了判断方法，我们就可以写二分的代码了：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int sit[100005];
int L,N,K;
inline bool check(int m)
{
	int y=K;
	int size=0;//确定当前的比较位置
	for(int i=1;i<N;i++)
	{
		if(y<0)
		{
			break;
		}
		if(sit[i]-size<=m)
		{
			size=sit[i];//成立则移动比较位置，比较下一组
		}
		else
		{
			size=size+m;//设置新的路标，前一个路标已满足，移动位置到新路标
			i--;//防止因为循环把之前的路标给移走了！
			y--;//减少可用新路标数
		}
	}
	if(y>=0)
	{
		return true;
	}
	return false;
}
int main()
{
	cin>>L>>N>>K;
	int t=0;
	while(t<N)
	{
		cin>>sit[t];
		t++;
	}
	int H=0,R=L;
	int ans;
	while(H<=R)
	{
		int mid=H+(R-H)/2;
		if(check(mid))
		{
			ans=mid;//记录
			R=mid-1;//可能存在更小的“空旷指数”，搜索左区间
		}
		else
		{
			H=mid+1;//答案只能是更大的“空旷指数”，搜索右区间
		}
	}
	cout<<ans;
}