首页 > 其他 > 详细

BZOJ 2456 mode(找众数)(暑假ACM1 F)

时间:2019-07-21 19:47:44      阅读:46      评论:0      收藏:0      [点我收藏+]

题意

给n个数,找出出现次数最多的数,保证出现n/2次.

100%的数据,n<=500000,数列中每个数<=maxlongint。

题解

正常思路是快排,然后统计答案。

可是这道题坑就坑在内存只有1M,所以连数组都不能开。

那么就有一种神仙做法了,既然有n/2个,那么其他数加起来都干不过他。

所以我们记录sum为当前众数还剩下的生命[滑稽],ans为当前众数,如果这一次读到的数是众数,他就可以吃口药,不是的话就要被打挨一滴血[很伤],如果没血了我们就要换个勇士来抗,站到最后的就是那个天选之子(众数)。

但是当前ans并不是最终答案,其他人攻击他有影响吗?

当然不会,他们自相残杀,对众数来说舒服得一批,可以用更少的血去搞定他们。

简直妙啊,hfu说这是一道简单题,和1+1一样,可能对于sxk来说是这样

技术分享图片
#include<cstdio>
using namespace std;
int n,ans,sum=0,x;
int main()
{
    
    scanf("%d",&n); 
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&x);
        if(!sum) {ans=x;++sum;}
        else
        {
            if(x==ans) ++sum;
            else --sum;
        }
    }
    printf("%d",ans);
    return 0;
}
View Code

还有万能头更占内存

BZOJ 2456 mode(找众数)(暑假ACM1 F)

原文:https://www.cnblogs.com/sto324/p/11222280.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!