2456: mode - #include <Seter> - using namespace Orz;

2456: mode

Seter posted @ 2011年9月24日 11:50 in BZOJ with tags Enumeration , 1718 阅读

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

RunID User Problem Result Memory Time Language Code Length Submit Time
155885 Seter 2456 Accepted 752 kb 184 ms C/Edit 397 B 2011-09-24 11:10:02

继续:为什么这几天经常莫名其妙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;
}
By Seter
  • 无匹配

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee