题解 P6282 【[USACO20OPEN]Cereal S】

2020-04-05 20:25:16


题面

这道题我是用队列做的。我们想一想少掉 $1$ 头奶牛,整个奶牛队列会发生什么变化

首先,最前面的那头奶牛走了,就空出来了他最喜欢吃的那包麦片了。

这包麦片可能会造成如下反应:

  • 一头奶牛原来吃的是它第 $2$ 喜欢的麦片,现在它吃自己第 $1$ 喜欢的了,使得又空出了一包麦片。
  • 一头奶牛原来没有东西吃,现在它吃到了它 第1/第2 喜欢的麦片。

我们可以写一个队列来计算这个东西,由于队列是先进先出,正好符合排队的顺序。

#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$ 的。