随便's Blog

Description

数据范围:  100%的数据，n<=500000，数列中每个数<=maxlongint。

数据范围太大，于是在网上找的了一个比较神奇的找众数的方法：

因为题中规定了众数一定多于二分之一，所以可以每次搜到不同的数都抵消，最后剩下的一定是最多的那个；

代码：

/**************************************************************
    Problem: 2456
    User: 1115825064
    Language: C++
    Result: Accepted
    Time:372 ms
    Memory:804 kb
****************************************************************/
 
 
#include<cstdio>
 
using namespace std;
 
int n,p;
int x,a;
int main()
{
    scanf("%d",&n);
    while(n--)
    {
     
        scanf("%d",&a);
        if(!p)
        {
            p=1;
            x=a;
        }
        else
        {
            if(x==a) p++;
            else p--;
        }
    }
    printf("%d",x);
    return 0;
}