题解 P6282 【[USACO20OPEN]Cereal S】
kradcigam
2020-04-05 20:25:16
[题面](https://www.luogu.com.cn/problem/P6282)
这道题我是用队列做的。我们想一想少掉 $1$ 头奶牛，整个奶牛队列会发生什么变化
首先，最前面的那头奶牛走了，就空出来了他最喜欢吃的那包麦片了。
这包麦片可能会造成如下反应：
- 一头奶牛原来吃的是它第 $2$ 喜欢的麦片，现在它吃自己第 $1$ 喜欢的了，使得又空出了一包麦片。
- 一头奶牛原来没有东西吃，现在它吃到了它 第1/第2 喜欢的麦片。
我们可以写一个队列来计算这个东西，由于队列是先进先出，正好符合排队的顺序。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &FF){
T RR=1;FF=0;char CH=getchar();
for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
FF*=RR;
}
const int MAXN=1e5+10;
int n,m,f[MAXN],s[MAXN],k[MAXN],sum[MAXN],x[MAXN],ans;
queue<int>v[MAXN];
int main(){
read(n);read(m);
for(int i=1;i<=n;i++)read(f[i]),read(s[i]);
for(int i=1;i<=n;i++){//x的值为1，表示吃它第1喜欢的麦片；x的值为2，表示它第2喜欢的麦片；x的值为3，表示他没吃到麦片
if(!k[f[i]])k[f[i]]=1,x[i]=1,ans++;
else if(!k[s[i]])v[f[i]].push(i),k[s[i]]=1,x[i]=2,ans++;
else v[f[i]].push(i),v[s[i]].push(i),x[i]=3;
}//暴力求出所有奶牛的情况
cout<<ans<<endl;
for(int i=1;i<n;i++){
int xx=f[i];//离开的那头奶牛最喜欢吃的麦片
ans--;
while(v[xx].size()){
int q=v[xx].front();
v[xx].pop();
if(x[q]==2){
xx=s[q];
x[q]=1;
}
if(x[q]==3){
ans++;
if(f[q]==xx)x[q]=1;
else x[q]=2;
break;
}
}
cout<<ans<<endl;
}
return 0;
}
```
复杂度分析：这个代码的复杂度其实是 $O(n)$ 的，因为我们最多队列里的每个元素访问 $1$ 次，然后队列里元素个数是 $2n$ 的。