P2397 yyy loves Maths VI (mode)
题目背景
自动上次redbag用加法好好的刁难过了yyy同学以后,yyy十分愤怒.他还击给了redbag一题,但是这题他惊讶的发现自己居然也不会,所以只好找你
题目描述
udp2:第一题因为语言性质问题，比赛结束后将所有c/c++的程序的内存调为2.2mb后重测。
他让redbag找众数
他还特意表示,这个众数出现次数超过了一半
一共n个数,而且保证有
n<=2000000
而且每个数<2^31-1
输入输出格式
输入格式：
第一行一个整数n
第二行n个整数
输出格式：
一行,这个众数
输入输出样例
输入样例#1：
5
2 3 3 3 3
输出样例#1：
3
说明
时间限制 1s
空间限制 3.5M(你没看错3.5M)
有人想水过,但我告诉你这空间是不够的
//kkksc03偷偷地说：你随便输出一个数字吧，都有1/2的几率。不过这可是乐多赛，值得不值得你看着办。所以最好想一想正解。
sol：感觉非常不可做，于是看了题解，感觉很fake
记一个变量ans表示答案，一个cnt表示ans出现的次数：如果读入的数与ans相同cnt++，否则cnt--，减到0时更换ans
Ps：自己的快读板子会MLE。。。
#include <bits/stdc++.h>
using namespace std;
int n;
int main()
{
int i,X,ans,cnt=;
scanf("%d",&n);
for(i=;i<=n;i++)
{
scanf("%d",&X);
if(ans==X) cnt++;
else if(cnt==)
{
ans=X; cnt=;
}
else if(ans!=X) cnt--;
}
printf("%d\n",ans);
return ;
}