来自FallDream的博客，未经允许，请勿转载，谢谢。

---

给定n个数，其中有一个数出现次数大于n/2，输出那个数  内存1MB

题解:先记下第一个数和此时的出现次数（一开始是1），然后一个个往后处理，如果这个数和现在几下的数不同，那么出现次数-1，否则出现次数+1。如果出现次数变为0，则把记下的数字改成现在这个数，这样一定能找到那个数。

比如3 2 4 3 3    (3,1)->(2,1)->(4,1)->(3,1)->(3,2)，找到了数字3

只能卡到40ms不知道rank1怎么卡到的36ms

#include
     
      using namespace std;char B[1<<15],*S=B,*T=B,C;int X;#define getc() (S==T&&(T=((S=B)+fread(B,1,1<<15,stdin)),S==T)?0:*S++)inline  int read(){     X=0;C=getc();    while(C < '0' || C > '9'){ C = getc();}    while(C >= '0' && C <= '9'){X = X * 10 + C - '0';C = getc();}    return X;}int n,a,b,x;int main(){    n=read();a=read();b=1;    for(register int i=2;i<=n;++i)        x=read(),        x==a?++b:--b,        b?0:(a=x,b=1);    printf("%d",a);    return 0;}