Eternity

Until The End

P2397 yyy loves Maths VI (mode)

发表于 分类于
本文字数： 2k 阅读时长 ≈ 2 分钟

摩尔投票的板子题。

为什么会记录这么简单的题捏（因为今年 NOI 考到了这个知识点）。

绝对众数

众数的定义是：在一个数列里出现次数最多的数。

绝对众数的定义在于，这个数出现的次数必须严格大于序列的一半。

举几个例子：

$A=\{0,1,2,3,3,3,3,3,3,3,3,4\}$ 中，绝对众数为 $3$ ；

$B=\{0,1,2,3,4,5,6,7,8,9\}$ 中，不存在绝对众数；

$C=\{1,1,1,1,1,2,2,2,2,2\}$ 中，同样不存在绝对众数。

题意

给定一个序列，求出该序列的绝对众数。

时间复杂度 $\mathcal O(n)$ ，空间复杂度 $\mathcal O(1)$ ，保证有解。

题解

有一种方法叫摩尔投票法，这个方法可以在时间复杂度 $\mathcal O(n)$ ，空间复杂度 $\mathcal O(1)$ 内解决保证有解的绝对众数问题，并在时空复杂度 $\mathcal O(n)$ 内解决不保证有解的绝对众数问题。

思路在于：同增异减。也称作对拼消耗或者相互攻击。

记录一个二元组 $(cnt,val)$ ，表示在当前 $1\sim i$ 中，投给 $val$ 的票数还剩下 $cnt$ 票。

我们在小的时候，可能都有一种解决追及问题的思路：

假如说一辆车甲的速度为 $v_1$ ，乙的速度为 $v_2$ ，且 $v_1>v_2$ ，那么，我们可以假设把两辆车的速度同时减去 $v_2$ ，那么，我们可以视作是乙车是不动的，甲车以一个很慢的速度向前行驶，然后就能轻松理解追及时间为 $\frac{d}{v_1-v_2}$ 了。

那么同样的，如果甲有 $x_1$ 票，乙有 $x_2$ 票。我们也可视作是没有人投给乙，而甲只有 $x_1-x_2$ 票，这就是摩尔投票算法的精髓所在。

摩尔投票算法的流程：

  1. 遍历一遍数列；
    1. 当遍历点为 $i$ 时，如果 $x_i\neq val$ ，则 $cnt$ 减 $1$ ；
    2. 否则 $cnt$ 加 $1$ 。

  2. 如果在某一个位置 $cnt=0$ 了，则更新 $val$ 为 $x_i$ 。

    结束，需要做的就是遍历一遍数列，时间复杂度 $\mathcal O(n)$ ，空间复杂度仅仅需要二元组 $(cnt,val)$ ，为 $\mathcal O(1)$ 。

然后你就会马上把这个算法 $\text{hack}$ 掉。

$Hack=\{3,3,3,2,2,2,1\}$ ，最后的答案是 $1$ ，那就寄寄了。

然后你会发现，这样的数据还有很多很多，但都有一个共同点，那就是无解的情况。

上述过程的确无法处理无解的情况，所以我们需要特判一下：

  • 在值域较小的情况下，可以开值域哈希表来存储 $Hash[val]$ 是否大于 $\frac{n}{2}$ 从而判断无解。
  • 在无法使用哈希的情况下，可以选择再次遍历序列，然后统计 $val$ 出现的次数。

这样的话，空间复杂度就会达到 $\mathcal O(n)$ 。

那么我们深度理解摩尔投票，最后得到的 $val$ 只是一个备选答案，而非序列的绝对众数，因为无法判断是否有解。

这样为什么是正确的呢？如果一个序列存在绝对众数 $d$ ，那么 $d$ 出现的次数一定大于了一半。我们假设只有 $d,!d$ 两个参赛选手，因为满足了 $cnt[d]\geq\frac{n}{2}$ ，也就满足了 $cnt[d]>cnt[!d]$ ，所以无论如何，$d$ 的票数都是最高的，即使在前半段的时候可能会被一些其他数字代替，但最后 $val$ 一定会被换回 $d$ 。

当然，这道题还有一个 $\mathcal O(n\log n)$ 的不算智慧的智慧法，直接将整个序列排序，则 $x_{\frac{n}{2}}$ 就是该序列的绝对众数。

此题保证有解，且空间限制为 $\text{5.00MB}$ ，所以不开数组。

AC Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int N,x,cnt,val;
int main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    read(N);
    for(re int i=1;i<=N;++i)
    {
        read(x);if(!cnt) val=x;
        cnt+=val==x?1:-1;
    }
    write(val);
    return 0;
}

后话

关于摩尔投票，它满足结合律。

就比如说两个序列 $(cnt_1,val_1)$ ，$(cnt_2,val_2)$ ，那么两个序列合并过后得到的绝对众数就是 $cnt$ 值较大的那个。

然后又可以被轻松 $\text{Hack}$ 掉。

$A_1=\{3,3,3,2,2,2,3\},val=3,cnt=1$

$A_2=\{1,1,1\},val=1,cnt=3$

这样得到的 $val=1$ ，然后我们会发现，$A_1,A_2$ 合并过后，根本就没有绝对众数。

然后就会发现，这个 $\text{Hack}$ 的解决方案和上述一致，绝对众数一定是摩尔投票的结果，但是摩尔投票的结果不一定是绝对众数。

所以需要特判。

相关文章