【BZOJ2456】mode 什么鬼boy题

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

Sample Output

3

HINT

100%的数据,n<=500000,数列中每个数<=maxlongint。

zju2132 The Most Frequent Number

咳咳,真的是鬼boy题,想了10分钟,看了看样例发现3是全部分开的,然后我就想是不是如果众数不连续出现就一定会在最后一个数出现(而且要求n是奇数,偶数的话一定会连续出现),然后旁边膜过题解的龙光告诉我说已经想到边上了。沃日,想不出了,然后去膜题解。

妈,我蠢死了。

正解:开4个变量n,a,x,y

x记录答案,y记录出现次数,如果下一个数a跟x不同,就y++,否则y--,如果y小于1,就将x替换为a

这样是对的,因为如果ans连续出现,那么必须连续出现相同次数才能将其抵消,但即使这样由于题目保证有解,因此ans的次数不能被抵消完全(如果被抵消完全相当于前面删去一段ans出现正好len/2次的序列,对答案无影响),而如果ans不连续出现那么之前证明了最后一个数一定是ans,于是也能出解。

代码如下:(什么多余的库都不能加,不然MLE给你看)

 

不如来评论一发?