自动搬运

查看原文

来自洛谷，原作者为

	PersistentLife **

搬运于2025-08-24 22:19:17，当前版本为作者最后更新于2020-04-16 19:14:52，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

博客阅读体验更佳

题目分析

本题用二分去做，我们二分 $D$ 的值，然后再 $\Theta(N+M)$ 贪心扫一遍，如果可以放得下就往大的找，否则往小的找。

我们二分的范围是从 $0$ 到 $\max b_i$，因为最坏的情况是每头牛都紧紧挨着一起，最优的情况是一头牛在数轴原点，另一头牛在数轴的最大值处。

虽然数轴是无限长的，但是在本题中，小于 $0$ 的部分对答案没有贡献，大于 $\max b_i$ 的部分也对答案没有贡献，所以我们假设数轴是从 $0$ 到 $\max b_i$ 的。

二分的复杂度为 $\Theta(\log(\max b_i))$，判断是否满足条件的复杂度为 $\Theta(N+M)$。

代码实现

回顾一下二分的模板:

while(l<r)
{
	mid=(l+r)/2+1;
	if(check()) l=mid;
	else r=mid-1;
}

复杂度为 $\Theta(\log(\max b_i))$。

下面是 $check$ 函数，因为要遍历每头牛和每一段草坪，所以复杂度为 $\Theta(N+M)$。

实现方法见注释：

bool check()
{
	int cur=a[1],cnt=1;//分别表示上一次放奶牛的位置和目前在用哪一块草坪 
	for(int i=2;i<=n;i++)//遍历每头牛，因为1号牛一定要放在a[1]的位置，所以可以在预处理里面解决 
	{
		if(cur+mid<=b[cnt]) cur+=mid;//如果这块草坪够放，就放在这块草坪上 
		else//否则 
		{
			while(cnt<m&&cur+mid>b[cnt]) cnt++;//找到下一个放牛的草坪 
			if(cur+mid>b[cnt]) return 0;//如果不够放，那么直接return 0 
			if(cur+mid<=a[cnt]) cur=a[cnt];  
			else cur+=mid;//同第一个if语句，放置这头牛 
		}
	}
	return 1;//若能放下就return 1 
}

完整代码：

#include<bits/stdc++.h>
#define int long long//懒得区分了
using namespace std;
int n,m,l,r,mid;
int a[123456],b[123456];
bool check()
{
	int cur=a[1],cnt=1;//分别表示上一次放奶牛的位置和目前在用哪一块草坪 
	for(int i=2;i<=n;i++)//遍历每头牛，因为1号牛一定要放在a[1]的位置，所以可以在预处理里面解决 
	{
		if(cur+mid<=b[cnt]) cur+=mid;//如果这块草坪够放，就放在这块草坪上 
		else//否则 
		{
			while(cnt<m&&cur+mid>b[cnt]) cnt++;//找到下一个放牛的草坪 
			if(cur+mid>b[cnt]) return 0;//如果不够放，那么直接return 0 
			if(cur+mid<=a[cnt]) cur=a[cnt];  
			else cur+=mid;//同第一个if语句，放置这头牛 
		}
	}
	return 1;//若能放下就return 1 
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>a[i]>>b[i];//读入
	sort(a+1,a+m+1);
	sort(b+1,b+m+1);//排好序，方便贪心
	l=0;r=b[m];//确定边界
	while(l<r)//二分
	{
		mid=(l+r)/2+1;
		if(check()) l=mid;
		else r=mid-1;
	}
	cout<<l;//输出
	return 0;//完结撒花
}