Time Limit: 1
Sec Memory Limit: 1 MB
Description
给你一个n个数的数列，其中某个数出现了超过n div 2次即众数，请你找出那个数。
Input
第1行一个正整数n。
第2行n个正整数用空格隔开。
Output
一行一个正整数表示那个众数。
Sample Input
5
3 2 3 1 3
3 2 3 1 3
Sample Output
3
HINT
100%的数据，n<=500000，数列中每个数<=maxlongint。
zju2132 The Most Frequent Number
这题如果内存限制没那么坑的话直接哈希或者sort就水过了……
可是这限制实在太坑了
这题有个神算法：因为保证有一个数出现了超过n/2次，所以直接用num保存数字、用ans保存出现次数，每次出现和它不一样的就把ans抵消掉1，最后一定会出现保存的数的ans>1。最后num就是答案
话说用快速读入就是优越……
#include<cstdio>
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,ans,num;
int main()
{
n=read();
while (n--)
{
int x=read();
if (ans==0){ans=1;num=x;continue;}
if(x==num) ans++;else ans--;
}
printf("%d",num);
}