http://www.zybbs.org/JudgeOnline/problem.php?id=2456

继续：为什么这几天经常莫名其妙RANK1……

今天看到小号过了这题于是发现这题数据更新重测了，于是又交了次就A了……

这个Matrix67说过，就是O(1)空间复杂度求众数（众数的个数大于总个数的一半，如果是一般意义上的众数那我就不会了……）。正解是保存前i个数的“众数”（其实不一定是众数，后面说）和此数出现次数与其他数出现次数的差（大于等于0）。

每次读入第i个数。（1）如果等于前面的那个众数，那么次数差加一。否则（2）如果次数差大于0就减一，（3）等于0说明这个新数是新的“众数”。

前两个都好理解，最后一个操作就难理解了。这个新数一定是前i个数的众数吗？答案是，虽然这个数不一定是前i个数的众数，不过在全部N个数读进来后得到的一定是众数。这是为什么呢？根据M67的说法，这个过程可以看成数之间的PK。

由于众数出现次数大于等于N/2，所以必定能PK掉其余所有数。如果最后得到的不是众数，那么这a（a>N/2）个数必定要找其他数PK并且被PK下去，那么其他数的个数b必定大于等于a，加起来得到N>N，而这是不可能的。

#include <stdio.h>
inline getint(){
    int re=0,ch=getchar();
    while(ch<'0'||ch>'9')if((ch=getchar())<=0)return -1;
    for(;ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;
    return re;
}main(){
    int n=getint(),a,b=0;
    while(n--){
        if(!b)a=getint(),b=1;
        else a==getint()?b++:b--;
    }printf("%d\n",a);
    return 0;
}

• inline
• block