题目地址：洛谷：【P2397】yyy loves Maths VI (mode) – 洛谷、BZOJ：Problem 2456. — mode

题目描述

给你一个n个数的数列，其中某个数出现了超过n div 2次即众数，请你找出那个数。

输入输出格式

输入格式：
第1行一个正整数n。
第2行n个正整数用空格隔开。

输出格式：
一行一个正整数表示那个众数。

输入输出样例

输入样例#1：

5
3 2 3 1 3

输出样例#1：

3

说明

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

题解

空间限制1MB，显然没法开数组了。
考虑一个奇特的算法，我们设置一个答案及它的计数器，每遇到与答案相同的数对计数器加1，不同的对计数器减1，计数器为0的时候更新答案为当前数字并且计数器重置为1。由于要求的众数个数大于n/2，众数在这个流程中计数器不会被归0，因此就能够把它找出来。
这真是一道没办法选择tag的题目呀。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>

inline char fgc() {
    static char buf[100], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100, stdin), p1 == p2) ? EOF : *p1++;
}

inline int readint() {
    register int res = 0;
    register char c = fgc();
    while(!isdigit(c)) {
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res;
}

int n, t, cnt, ans;

int main() {
    n = readint();
    while(--n) {
        t = readint();
        if(ans == t) ++cnt;
        else if(!cnt) { ans = t; cnt = 1; }
        else --cnt;
    }
    printf("%d", ans);
}