Majority Opinion (USACO Bronze 2024 January)

相邻的牛投票按多数决定吃哪种草，问哪些草可能成为所有牛都吃的草，

我们考虑是否存在规律简单的贪心算法，从相邻三头牛（投票的最少数量）的角度，可以找到以下规律：

三头牛中，如果有两头牛吃了同一种草，那么第三头牛也会吃这种草。

有三头牛吃了同一种草之后，每次往边上扩展一头牛，就也能说服这头牛吃这个草，所以可以一直扩展到所有牛。

倒过来，仔细推演一下会发现，如果有一种草成功了，那必然能找到三头牛中至少两头吃这种草，因为至少能找到一个区间，这种草占比超过一半，那么可以证明至少存在一个位置，这种草中间最多隔着一个位置，那这三个位置中就有两个位置是我们所说的草，得证。

所以我们从左到右扫描一遍，如果x[i] == x[i-1] 或者 x[i] == x[i-2], 则x[i]就是一个合格的答案。如果没有合格的答案，输出-1。

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n, T;
int valid[200005];
 
int main() {
    scanf("%d", &T);
    for (int test = 0 ; test < T; test++) {
        memset(valid, 0, sizeof(valid));
 
        scanf("%d", &n);
        int last = -1, last2 = -1, x;
        for (int i = 0; i < n; i++) {
            scanf("%d", &x);
            if (x == last || x == last2)
                valid[x] = 1;
            last2 = last;
            last = x;
        }
 
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (valid[i]) {
                if (cnt) printf(" ");
                printf("%d", i);
                cnt++;
            }
        }
        if (cnt == 0)
            printf("-1\n");
        else
            printf("\n");
    }
 
    return 0;
}