自动搬运

查看原文

来自洛谷，原作者为

	GONGX ​ | 最后在线时间: 2025/8/24 8:39

搬运于2025-08-24 22:54:59，当前版本为作者最后更新于2024-02-05 20:19:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意简述

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;
}