题解 P1407 【工资】

zqy1018 · 2016-09-25 13:02:03 · 题解

由于题目条件中给出了“众数出现次数一定>(n/2)”的条件，故可以用记录位的方法解决。

开一个长度为32的数组cnt来记录每一个位上1出现的次数，对于每一个数q，当q&(1<<t)为1时，令cnt[t]++。

这么做的原因是当这个位上1出现的次数大于(n/2)时，众数的这个位上一定是1。

最后检查每一位上1出现的次数，拼出答案即可。

<codec>
for(int i=0;i<32;i++)
    if(cnt[i]>n/2)
        ans|=(1<<i);
printf("%u\n",ans);
</codec>