自动搬运

查看原文

来自洛谷，原作者为

	呆瓜yy **

搬运于2025-08-24 21:35:09，当前版本为作者最后更新于2019-03-16 10:05:06，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一篇很水的题解

首先，观察题目可知，既然N很大，K很小（假装是吧），那么突破口就在于K

假设一下，如果知道从哪里把奶牛分开，题目就很简单了，但如果用for循环n硬做，肯定会超时的。于是，根据科学猜题法，要做的是for循环k来找断点

以下是很水的时间为ans*k的算法：

首先从1-n枚举第i头奶牛（会优化的，理论上不会超时），作为第ans张照片的第一头奶牛

然后在k个限制中找到a>=i对应的最小b值（当然，这需要排序）

最后ans++，i直接跳到找到的b

关于这个方法的解释：

如果我们要确定一张照片的奶牛，则必须保证这张照片中的奶牛关系友好。换句话说，就是找到第一只与照片中的奶牛关系不好的奶牛的前一只作为这张照片的最后一只奶牛。

于是我们可以枚举第一头奶牛i，并在k个限制中寻找第一只不能存在于同一照片中的奶牛（注意：若当前的a<i，则对应的b对于这张照片无影响）

很水的代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
namespace lyy
{
	int n,k,j,i,yy,ans;
	const int INF=0x7f7f7f7f;
	struct photo
	{
		int a,b;
	}p[1005];
}
using lyy::n;//忽略这些细节，只是为了好玩
using lyy::k;
using lyy::p;
using lyy::i;
using lyy::j;
using lyy::yy;
using lyy::ans;
using lyy::INF;
bool cmp(lyy::photo x,lyy::photo y)
{
	if(x.a!=x.b)
	  return x.a<y.a;
	return x.b<y.b;
}
int main()
{
//	freopen("photo.in","r",stdin);
//	freopen("photo.out","w",stdout);
	cin>>n>>k;
	for(i=1;i<=k;i++)
	{
		cin>>p[i].a>>p[i].b;
		if(p[i].a>p[i].b)
		  swap(p[i].a,p[i].b);
	}
	sort(p+1,p+k+1,cmp);
	for(i=1;i<=n;)
	{
		yy=INF;
		for(j=1;j<=k;j++)
	      if(p[j].a>=i)
	        yy=min(yy,p[j].b);
	    ans++;
	    i=yy;
	}
	cout<<ans;
	return 0;
}