2132.cpp

ZJU ACM 2132。 ZOJ排名第一的代码。

/*
由于最高频数的频度大于 n/2, 故若将其排序, 则第 n/2+1 必为此数. 问题是这就要
求一个 1Mb(4*250000) 的数组, 不符合题目的数据要求.
    不过, 如果数组是有序的, 那么中间连续至少 n/2+1 个 X, 两头非 X 的数若与 X
逐一匹配, 则必有剩余的 X 没能被匹配. 显然, 这个性质与数组是否有序无关.
    如果将 X 理解为进栈, 非 X 理解为出栈, 那么最后栈必非空且栈顶为 X.
    可是, X 是未知的, 这个理解不能解决问题. 然而注意到存在足够多个相同的 X,
因此如果将不相同的数互相抵掉, 则无论如何剩余的数还是 X. 所以, 可以建立一个栈,
栈空时总进栈, 栈非空时若当前元素与栈顶元素相同则进栈, 否则出栈. 这样, 最后栈
也必非空且栈顶元素必是 X.
    因为栈中元素总相同, 故只须记一个Copy及栈指针. 显然, 这是 O(n) 时间和 O(1)
空间复杂度的算法, 而且是 Online 的.
    下面程序用 s 记录栈中元素, p 记栈指针, c 记当前元素.
*/

#include <stdio.h>

const int L = 1000;

char buf[L+1];
bool b[128];
int l;

int geti() {
  int r=0, ch, f=0;
  if (buf[l]=='-') f=-1,l++;
  while(b[ch=buf[l++]])r=10*r+(ch&0xF);
  if (ch==0) { l=0; fgets(buf,L+1,stdin); while(b[ch=buf[l++]])r=10*r+(ch&0xF); }
  return f^(r+f);
}

int main() {
  for (int i='0'; i<='9'; i++) b[i]=1;
  int n, c, s, p;
  while (fgets(buf,L+1,stdin)!=NULL) {
    l=0; n=geti(); s=geti(); p=1;
    for (int i=1; i<n; i++) { c=geti(); p?(c==s?++p:--p):(s=c,p=1); }
    printf("%d\n",s);
  }
  return 0;
}