「洛谷P2397」 yyy loves Maths VI (mode) 解题报告
2024-09-06 16:41:49
P2397 yyy loves Maths VI (mode)
题目背景
自动上次redbag用加法好好的刁难过了yyy同学以后,yyy十分愤怒.他还击给了redbag一题,但是这题他惊讶的发现自己居然也不会,所以只好找你
题目描述
udp2:第一题因为语言性质问题,比赛结束后将所有c/c++的程序的内存调为2.2mb后重测。
他让redbag找众数
他还特意表示,这个众数出现次数超过了一半
一共n个数,而且保证有
n<=2000000
而且每个数<2^31-1
输入输出格式
输入格式:
第一行一个整数n
第二行n个整数
输出格式:
一行,这个众数
输入输出样例
输入样例#1:
5
2 3 3 3 3
输出样例#1:
3
说明
时间限制 1s
空间限制 3.5M(你没看错3.5M)
有人想水过,但我告诉你这空间是不够的
//kkksc03偷偷地说:你随便输出一个数字吧,都有1/2的几率。不过这可是乐多赛,值得不值得你看着办。所以最好想一想正解。
思路
题目意思很简单,就是求众数。然鹅,,,,,空间贼小,,,,
这里的突破口就是这个众数出现次数超过了一半
,所以我们可以运用一种神奇的方法。
我们不断将两个不同的数字删去,最后剩下的数肯定相同的,它就是众数。
为什么呢?假设最坏的情况——都是众数与其它数一起删去,但是这个众数出现次数超过了一半
,所以众数不可能全部被消去,剩下的数就是众数。如果非众数与非众数相消去,众数剩下的会更多,会更优。
这好像叫摩尔投票法。
代码
#include<bits/stdc++.h>
using namespace std;
int n, a, b, t;
int main(){
scanf( "%d", &n );
scanf( "%d", &a ); b = 1;
for ( int i = 2; i <= n; ++i ){
scanf( "%d", &t );
if ( t == a ) b++;
else if ( b ) b--;
else a = t, b = 1;
}
printf( "%d\n", a );
return 0;
}
拓展
摩尔投票算法可以拓展到 出现次数超过1/3,甚至1/k的情况。
只要把一次消掉2个数改成消掉k个数就可以了。
最新文章
- java.lang.NoSuchFieldError: org.apache.http.message.BasicLineFormatter.INSTANCE
- NYOJ题目893十字架
- DOM扩展之Selectors API
- /lib /usr/lib /usr/local/lib区别
- selenium By 元素定位详解
- JS比较好用的一些方法搜集
- 《C标准库》—之<;assert.h>;实现
- 获取 UIWebView中用户所点击的图片URL
- error: device not found - waiting for device -
- SQL语句 常用条件判断
- Hibernate 多对多映射
- Session小解
- 微信支付坑:url未注册
- 每天一道Java题[1]
- SpriteBuilder中的loadAsScene:方法的返回值
- luoguP2526_[SHOI2001]小狗散步_二分图匹配
- 「Continuous_integration, CI」为什么要持续集成?
- Apache为mysql以及自己的项目设置虚拟路径
- GFF高仿QQ客户端及服务器
- AVAudioSesion和AVAudioPlayer的基本使用
热门文章
- react+antd 点击分页为上次操作结果
- Project Euler Problem 26-Reciprocal cycles
- H3C TCP与UDP的对比
- 数(aqnum)
- 如何创建私有pod三方库
- php Restful设计
- The &#39;decorators&#39; plugin requires a &#39;decoratorsBeforeExport&#39; option, ...(npm start报错)
- Python--day25--接口类多继承
- [转]C#中 ??、 ?、 ?: 、?.、?[ ] 问号
- Gyn 100989 ";1D Cafeteria (B)";(set+lower_bound)