题解：P1694 [USACO19FEB] The Great Revegetation B

Licis_Subway · 2024-06-15 14:01:10 · 题解

本题解主要使用贪心算法。

1. 思路

本题我们看到“Farmer John 知道没有一块草地受到多于 3 头奶牛的喜爱。”这句话后，就可以明白一定可以使用贪心。

为了保证答案为字典序最小的答案，我们可以进行逐位进行求解。求完第一块草地的解后，我们再求后面的草地的解。

2. 做法

这样的话，我们就可以遍历每一个草地并进行枚举：

• 如果当前草地有牛喜欢……
  • 那头牛喜欢的另一个草地和当前草地一样？
    • 枚举下一种草（当前草不能使用）。
  • 否则……
    • 将当前草地匹配当前草类型。

就像这样：

for(int i=1;i<=m;i++)
  scanf("%d%d",&a[i].first,&a[i].second);

接下来，枚举每一个草：

for(int i=1;i<=n;i++)//每一个草地
{
    int grasstype=1;
    for(;grasstype<=4;grasstype++)//枚举四种草哪种可以
        if(check(i,grasstype))//如果可以
        {
            ans[i]=grasstype;//设置答案
            break;
        }
}

接下来，是重点部分（check 子函数）

bool check(int grass,int x)
{
    set<int> cows=findcow(grass);//有哪些牛喜欢这片草地
    set<int>::iterator it=cows.begin();
    for(;it!=cows.end();it++)//枚举这些牛
    {
        if(a[*it].first==grass)//如果第一个存储的是当前草地（第二个为目标草地）
        {
            if(a[*it].second>=grass) continue;//检查目标草地是否还未存储答案
            if(ans[a[*it].second]==x) return false;//如果相等，则当前答案错误。
            else continue;
        }
        else//同理
        {
            if(a[*it].first>=grass) continue;
            if(ans[a[*it].first]==x) return false;
            else continue;
        }
    }
    return true;
}

findcow 子函数用来找出所有喜欢当前草地的牛，大概这样写：

set<int> findcow(int grass)
{
    set<int> ans;
    for(int i=1;i<=m;i++)
        if(a[i].first==grass||a[i].second==grass) ans.insert(i);
    return ans;
}

到这里，本题就结束了。

3.完整代码

这里

关于本题一定有解

这里为大家证明一下为什么本题一定有解。

证明本题一定有解