AcWing 5524. 多数意见
原题链接
简单
作者:
O₂
,
2024-02-25 19:23:32
,
所有人可见
,
阅读 20
思路
本题问最后有几种干草有可能会成为所有奶牛统一喜欢的干草,我们可以枚举一个长度为3的滑动窗口,
如果一种干草在区间内出现次数大于等于2,那么就把她加到答案里,因为只要这种干草在这个区间里出现
次数大于等于2,那么当前区间里的所有数都会变成它,我没只要在把这个区间往左边或右边扩展一个,那么
被扩展到的那头奶牛的喜欢的干草的类型就会变成那个区间中的奶牛喜欢的干草的类型,知道整个区间都
会变成最开始的区间内的奶牛喜欢的干草的种类
C++ 代码
#include<unordered_map>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e5+10;
int n,cnt,a[N],res[N];
bool st[N];
int main(){
int T;
cin>>T;
while(T--){
cin>>n;
cnt=0;
memset(res,0,sizeof res);
memset(st,false,sizeof st);
for(int i=1;i<=n;i++) cin>>a[i];
if(n==2){
if(a[1]==a[2]) cout<<a[1]<<endl;
else cout<<-1<<endl;
}else{
for(int i=1;i<=n-2;i++){
unordered_map<int,int>mp;
for(int j=i;j<=i+2;j++){
mp[a[j]]++;
if(mp[a[j]]==2){
res[cnt++]=a[j];
break;
}
}
}
if(!cnt) cout<<-1<<endl;
else{
sort(res,res+cnt);
for(int i=0;i<cnt;i++){
if(!st[res[i]]) cout<<res[i]<<" ";
st[res[i]]=true;
}
cout<<endl;
}
}
}
return 0;
}