摩尔投票相关应用

最基本的摩尔投票

摩尔投票法(Boyer–Moore majority vote algorithm)是一个比较冷门的算法，最初算法解决的问题是如何在任意多的候选人（选票无序），选出获得票数最多的那个。在算法竞赛中我们较多的用它来解决绝对众数的问题。

先从最基本情况出发，思考一个问题，如何找到n个数中的绝对众数，这里的绝对众数指的是这个数的数量占所有数的比例超过1/2。这个问题很直接的思路是可以直接排序做，但是时间复杂度并不优秀，并且如果要保留原序列，还需要额外的空间开销。不是一个很好的方式，这时候，我们就可以用摩尔投票的思想来解决这个问题。

首先说明一个事实，就是区间绝对众数只有1个数，摩尔投票算法是基于这个事实：每次从序列里选择两个不相同的数字删除掉（或称为“抵消”），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个。

如果这样说很抽象，举个简单的例子帮助理解，又n个人打群架，大家都有自己的阵营，但是有一个阵营达成了垄断，就算其他所有阵容联合起来，也打不过这个最大的阵容。所以每次我们只要保证不打内战，每次让两个元素同归于尽，最后剩下的就是要找的这个元素。

实现起来也很容易，我们只需要记录一个元素now表示当前的元素，一个元素cnt记录当前元素now的数量。对于一张新元素，如果和now相同，cnt++，否则cnt--，如果cnt为0时候，新元素成为新的now。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    ll now = 0, cnt = 0;
    for (int i=1;i<=n;i++)
    {
        if (cnt == 0)
            now = a[i];
        if (now == a[i])
            cnt++;
        else
            cnt--;
    }
    return 0;
}

注意这个算法只有在绝对众数存在的时候才能确保返回的答案正确性。、

这个算法是 O(n) 时间复杂度、 O(1) 空间复杂度的。

扩展摩尔投票

可以证明，出现次数超过 n/k 的数最多只有 k−1 个。否则必然违背数总共只有 n 个或者当前统计的是出现次数超过 n/k 的数的前提条件。

有了这个前提，我们还是按照上面的标准执行摩尔投票，在遍历数组过程中依次检查这k-1个候选数。执行即可

上述做法正确性的关键是：若存在出现次数超过 n/k 的数，最后必然会成为这 k−1 个候选者之一。

这个结论可以通过反证法证明，也可以直接感性理解一下，或者直接当结论处理，感兴趣可以阅读这篇博客了解更多摩尔投票（绝对众数） - OIer某罗 - 博客园 (cnblogs.com) 。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll now[N],cnt[N];
int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    for(int i=1;i<=n;i++)
    {
        int q = find(now,now+n,a[i])-now;
        if (q != n { // 如果当前票投给了候选人之一
            cnt[q]++;
            continue;
        }
        int j = find(cnt,cnt+n,0)-cnt;
        if (j != n) { // 如果当前存在一个位置"虚位以待"
            now[j]=a[i];
            cnt[j] = 1;
            continue;
        }
        for(int j=1;j<=n;j++)
        cnt[j]--;
    }
    return 0;
}

区间绝对众数

区间绝对众数问题也可以利用摩尔投票解决，这需要在线段树上进行摩尔投票。

首先摩尔投票其实是不符合结合律的，但是其实在这个维护区间众数的过程中，cnt并不关键，如果区间存在绝对众数，他是可以交换顺序记票的，所以仍然可以得到正确的绝对众数，只是需要额外验证。所以，我们可以在线段树上进行摩尔投票。在合并左右两个区间时，相当于是先对左右两边分别进行摩尔投票，再对两边抵消后的结果进行摩尔投票。

今年的noi 签到题就是这样一道利用了摩尔投票的数据结构题，一定程度上算是某种套路题，感兴趣可以尝试做做看。