Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom2年前

10/26
19:43
未分类

[bzoj 2456] mode

00:00/00:00

1403243817332_middle   0b1b7913aacde097

♦♦♦♦♦♦   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

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

一开始没注意到空间只有1MB就MLE了 QAQ,做法:把每个与它不同的数抵消,因为要求的是出现次数超过n div 2次的数,所以那个剩下的数就是答案

c++:

pascal:

20140516223632_xAkEu.thumb.600_0

 

[bzoj 2456] mode