【题解】P10131 [USACO24JAN] Majority Opinion B

· · 题解

题意简述

Farmer John 要弄清楚要为他的奶牛们购买什么类型的干草。

Farmer John 的 N 头奶牛编号为 1 到 N，每头奶牛都喜欢一种干草 h_i。他希望他的所有奶牛都喜欢同一种干草。

为实现这一目标，Farmer John 可以主持焦点小组访谈。每次焦点小组访谈让从 i 到 j 的连续范围内的所有奶牛聚在一起参加。如果有一种干草是小组中超过一半的奶牛喜欢的，则此次焦点小组访谈结束后，所有奶牛最终都会喜欢这种干草。

Farmer John 想知道哪些类型的干草有可能变得同时受到所有奶牛的喜爱。他一次只能主持一个焦点小组访谈，但为了使所有奶牛都喜欢同一类型的干草，他可以根据需要任意多次地主持焦点小组访谈。

解题思路

首先，我们可以先想一想当 n=2 时，若小组内两头奶牛都喜欢同种类型的干草则有解；当 n=3 时，则当组内有任意两头奶牛喜欢同种类型的干草时有解。

然后很容易即可推出，若奶牛 i-1 和奶牛 i 或 奶牛 i 和奶牛 i-2 喜欢同类型的干草，那么奶牛 i-2，奶牛 i-1 和奶牛 i 将可以同时喜欢奶牛 i 所喜欢的干草类型。

而对于任何奶牛数大于 3 的焦点访谈小组，我们一定能从中找到一个有 3 头奶牛的焦点访谈小组。若有干草类型满足上面推导的关系，则这种类型的干草将可以受到所有奶牛的喜爱。

代码展示

#include<iostream>//当然，也可以使用万能头代替此头文件
using namespace std;
int T,n,h[100005];
bool f[100005];//用于标记此干草类型是否可能受到所有奶牛的喜爱 
int main(){
    scanf("%d",&T);//输入操作次数
    while(T--){
        scanf("%d%d",&n,&h[1]);
        for(int i=2;i<=n;i++){
            scanf("%d",&h[i]);
            if(!f[h[i]]&&(h[i]==h[i-1]||h[i]==h[i-2]))//判断h[i]是否符合要求
                f[h[i]]=true;//符合要求时打标记 
        }bool flag=true;//用于判断是否无解 
        for(int i=1;i<=n;i++)
            if(f[i])printf("%d ",i),f[i]=flag=false;//别忘记将f数组清零
        if(flag)printf("-1");//无解时，输出-1
        putchar('\n');//最后注意要输出换行符
    }
return 0;
}