自动搬运

查看原文

来自洛谷，原作者为

	cyrxdzj 以代码为笔，绘美好画卷。

搬运于2025-08-24 22:18:12，当前版本为作者最后更新于2021-07-26 21:38:39，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一、思路

首先，$R$ 越大，干草就越有可能被引爆完。

显然，这需要使用二分算法。

$R$ 的最小值为 $0$（每个奶牛炸一堆干草），最大值为 $10^9\div2$（全场干草一个奶牛下来就被炸完了）。

二分算法的精髓在于 check 函数，用于检查这个答案是否符合题意。那么，这道题的 check 应该怎么做呢？

二、检查函数

首先，干草堆的位置必须有序。这不难，一个 sort 函数下来就搞定，数据范围也不大。

我们可以定义一个变量 position，代表当前已被发射的奶牛，最远可以炸到那个点上。初始值为 -0x7fffffff，这是 int 型的最小值。

然后，顺序遍历所有干草堆。如果 position 加上当前假设的距离小于这个干草堆的位置，就说明这个干草堆还没被炸到，因此要再多一个奶牛，并将 position 更新为当前干草堆的位置加上当前假设的距离。

如果使用的奶牛数量大于 $K$，就说明这个距离太小，返回 false。

到了最后，如果使用的奶牛数量不大于 $K$，就说明这个距离足够了，返回 true。

三、坑点

记得排序！

四、完整代码

#include<cstdio>
#include<algorithm>
using namespace std;
int n,k;
int grass[50005];
int left,right=1000000000;
int middle;
int ans;
bool check(int x)//检查函数。
{
	int use_cow=0,position=-0x7fffffff;
	for(int i=1;i<=n;i++)
	{
		if(position+x<grass[i])
		{
			use_cow++;
			position=grass[i]+x;
			if(use_cow>k)
			{
				return false;
			}
		}
	}
	return true;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&grass[i]);
	}
	sort(grass+1,grass+1+n);//记得排序！ 
	while(left<=right)//二分。
	{
		middle=(left+right)>>1;
		if(check(middle))
		{
			right=middle-1;
			ans=middle;
		}
		else
		{
			left=middle+1;
		}
	}
	printf("%d\n",ans);
	return 0;//完结撒花！
}

By dengzijun