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

题意

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

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

题解

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

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

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

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

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

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

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

#include
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;
}

还有万能头更占内存

转载于:https://www.cnblogs.com/sto324/p/11222280.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！