题目描述 Description
FFF 团卧底在这次出题后就知道他的菊花可能有巨大的危险,于是他提前摆布好了菊花阵,现在菊花阵里有若干朵菊花,出现次数最多的那一朵就是出题人的,你的任务是需要找出出题人的菊花。
输入描述 Input Description
第一行为 n
第二行为 n 朵菊花
输出描述 Output Description
一行,为出题人的菊花
样例输入 Sample Input
5
1 1 1 2 3
样例输出 Sample Output
1
数据范围及提示 Data Size & Hint
对于 100%的数据,n<=5000000,每个数都在 int 范围内,保证出题人的菊花出现的次数大于等于[n/2]
Solution
这题真是日了狗
乍一眼看就是BZOJ2456: mode吧 fractal128的题解（别指望看懂他说什么
然而
。。。
注意
。。。
出题人的菊花出现的次数大于等于[n/2]
对是大于等于
于是在偶数情况下出现了可能抵消的情况
然后你的程序就炸了。
官方题解：
找众数的题，这题可以有很多种办法，出题人在此提供几种正确性尚待证明
的算法。
1.把所有区间变成10 份，在每份区间里区间抽样，抽样之后在选出的区间里再
次抽样，然后综合每个区间的抽样，得出答案。
2.读入一半数据qsort 即可（会被卡）
3.读入一半数据qsort,剩下一半二分
4.利用众数占了整个区间的一半以上，把不同的数“相互抵消”，剩下的一定是众数，
但是在此题中有坑，需要特判，偶数情况下，众数可能跟非众数抵消，所以需要
用数组提前预处理。
代码还没打。