题解 P6282 【[USACO20OPEN]Cereal S】

PersistentLife · 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)。

实现方法见代码注释：