自动搬运

查看原文

来自洛谷，原作者为

	PersistentLife **

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

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

以下是正文

博客阅读体验更佳

Level $1$：

我们很容易想到，从 $0$ 到 $N-1$ 枚举，然后模拟奶牛选择麦片的过程。

其中 $h_i$ 表示第 $i$ 种麦片被选择的情况，$c_i$ 表示第 $i$ 头奶牛喜欢的麦片。

#include<bits/stdc++.h>
using namespace std;
const int N=123456;
struct cow
{
	int f,s;
}c[N];
bool h[N];
int n,m;
void init()
{
	for(int i=1;i<=n;i++) h[i]=1;
}
void solve(int x)
{
	int ans=0;
	init();
	for(int i=x+1;i<=n;i++)
	{
		if(h[c[i].f])
		{
			ans++;
			h[c[i].f]=0;
		}
		else if(h[c[i].s])
		{
			ans++;
			h[c[i].s]=0;
		}
	}
	cout<<ans<<endl;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>c[i].f>>c[i].s;
	for(int i=0;i<n;i++) solve(i);
	return 0;
}

这份代码只有 $30$ 分，其余 TLE 了。

我们从 $0$ 到 $N-1$ 都进行了枚举，而每次算答案的时候要遍历每一头牛，所以时间复杂度为 $\Theta(N^2)$。

这里 $N \le 10^5$，所以我们的复杂度是不行的。

因为我们要算出 $N$ 个答案，所以复杂度至少为 $\Theta(N)$，故我们只能优化 $solve$ 函数。

Level $2$：

我们想想，当减少一头牛时，会发生什么情况？

• 如果它选择了麦片，那么它的麦片可能被其他奶牛选择；

• 如果没有选择麦片，那么答案不会改变。

但是，这样还是要找一下有哪头奶牛需要这个麦片，所以优化不了多少。

怎么办呢？大家跟我一起念：我们遇到什么困难，也不要怕，微笑着面对它……

如果我们增加奶牛，即倒着求每个答案，最后倒着输出就行了。

如果增加一头奶牛，又会出现什么情况呢？

• 如果它最喜欢的麦片没有被选择，那么它就会选它，且不影响其他奶牛；

• 如果它最喜欢的麦片被选择，因为它的优先级比其他牛都高，所以会把其他牛的麦片“抢”过来，其他牛只能“退而求其次”。

这样代码就很好写啦，递归求解即可，因为所有奶牛最多选两次，所以 $solve$ 函数的复杂度是 $\Theta(1)$ 的，整个代码的时间复杂度为 $\Theta(N)$。

实现方法见代码注释：

$c_i$ 表示第 $i$ 头奶牛的喜好，$h_i$ 表示拿走第 $i$ 种麦片的牛的编号，$res_i$ 表示移走 $i-1$ 头牛的答案，$cur$ 是计算答案的计数器。

因为领麦片的牛越多，领到麦片的牛就越多，所以越往后面，$cur$ 就越大，故每次计算的时候 $cur$ 不需要清零。

#include<bits/stdc++.h>
using namespace std;
const int N=123456;
struct cow
{
	int f,s;
}c[N];
int h[N],res[N],n,m,cur;
void solve(int x,int y)//x表示目前是哪一头牛选麦片，y表示目前要选择的麦片 
{
	if(h[y]==0)//最喜欢的未拿走 
	{
		h[y]=x;//拿走它
		cur++;//计数器加一 
	}
	else if(h[y]>x)//虽然麦片被拿走，但是当前的牛有排在前面，依然可以拿走
	{
		int z=h[y];//要重选的奶牛编号 
		h[y]=x;//拿走，这里不需要加一，因为之前拿走麦片的牛和现在拿走麦片的牛都是牛 
		if(y==c[z].f) solve(z,c[z].s);//如果"抢"过来了，那么另一头牛就要重选 
	} 
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>c[i].f>>c[i].s;
	for(int i=n-1;i>=0;i--) solve(i+1,c[i+1].f),res[i+1]=cur;
	for(int i=1;i<=n;i++) cout<<res[i]<<endl;
	return 0;
}