BZOJ.2456.mode(绝对众数)
2024-10-13 08:23:10
\(Description\)
限制空间(只能保留两个变量),求给定n个数中出现次数超过\(\frac{n}{2}\)的数。
\(Solution\)
维护两个变量,\(now\)和\(cnt\);枚举\(x\):
- \(now\neq a_i\):若\(cnt=0\),则\(now=a_i,cnt=1\),否则\(cnt--\)。
- \(now=a_i\):\(cnt++\)。
最后的\(now\)为答案。因为绝对众数出现次数超过了一半。
这题更好的方式是出成交互:Majority Element。
//920kb 56ms
#include <cstdio>
#include <cctype>
//#define gc() getchar()
#define MAXIN 100000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
char IN[MAXIN],*SS=IN,*TT=IN;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
int main()
{
int n=read(),now,cnt=0,t;
while(n--)
if((t=read())==now) ++cnt;
else if(!cnt) now=t, cnt=1;
else --cnt;
printf("%d\n",now);
return 0;
}
最新文章
- Python类属性,实例属性
- delphi 10 seattle 安卓服务开发(三)
- virtualbox 安装ubuntu
- javascript 深拷贝
- RabbitMQ介绍2 - AMQP协议
- 使用.net FtpWebRequest 实现FTP常用功能 上传 下载 获取文件列表 移动 切换目录 改名 .
- Android特效--粒子效果之雨
- 安装vmware tools失败解决方法
- Struts 2.x仍然明显落后于时代。 Struts 2.x这一类老牌Web MVC开发框架仅能用于开发瘦客户端应用,无法用来开发对于交互体验要求更高的应用。
- OC类方法的调用
- Linux Smaba服务器配置
- python net-snmp 的使用
- 【一天一道LeetCode】#299. Bulls and Cows
- vector的用法小结(待补全
- 了解AutoCAD对象层次结构 —— 4 —— 符号表
- qt无法使用终端启动的解决方法
- [UE4]根据时间、速度进行插值:Finterp to Constant
- 运行vbs脚本
- Mercurial和Git的主要区别(zz)
- PHP百万级数据导出方案(多csv文件压缩)