2456: mode
Time Limit: 1 Sec Memory Limit: 1 MB
Submit: 4798 Solved: 2009
[Submit][Status][Discuss]
Description
给你一个n个数的数列,其中某个数出现了超过n div 2次即众数,请你找出那个数。
Input
第1行一个正整数n。
第2行n个正整数用空格隔开。
Output
一行一个正整数表示那个众数。
Sample Input
3 2 3 1 3
Sample Output
HINT
100%的数据,n<=500000,数列中每个数<=maxlongint。
zju2132 The Most Frequent Number
Source
/*
* Author: lyucheng
* Created Time: 2017年05月14日 星期日 17时17分40秒
* File Name: /media/lyucheng/Work/ACM源代码/数学--数论/乱搞/BZOJ-2456.cpp
*/
/* 题意:给你一个n个数的序列,ai<=longmaxint,然后让你求出出现次数超过 n/2的众数
*
* 思路:map映射不可行,可以离散化优化一下,还是超时,可能不是超时的问题,应该是超内存,显然500000个LL开数组肯定会超时的
* 所以不能开数组,看了题解才发现这个神奇的算法,众数肯定是出现次数最多的那个数,现在让所有不相同的数进行两两抵消
* 那么剩下的肯定是数量最多的那一个了
* */
#include <cstdio>
int n;
int x;
int now;//当前遍历到的数
int res;//表示现在相同的数的数量
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout;
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%d",&x);
if(x==now) res++;//如果两个数相等,那么相等的数量+1
else if(res==){//如果当前没有相等的数了
now=x;res=;
}else res--;//不相等就-1
}
printf("%d\n",now);
return ;
}
2456: mode的更多相关文章
-
BZOJ 2456 杂题 卡内存
2456: mode Time Limit: 1 Sec Memory Limit: 1 MBSubmit: 3702 Solved: 1551[Submit][Status][Discuss] ...
-
POJ 2456 (二分)
题目链接: http://poj.org/problem?id=2456 题目大意:n个房子,m头牛,房子有一个横坐标,问将m头牛塞进房子,每两头牛之间的最大间隔是多少. 解题思路: 不难看出应该二分 ...
-
【BZOJ】2456: mode
http://www.lydsy.com/JudgeOnline/problem.php?id=2456 题意:给一个$n<=500000$的数列,求出现次数超过$\lfloor \frac{n ...
-
BZOJ 2456: mode 水题
2456: mode Time Limit: 1 Sec Memory Limit: 256 MB 题目连接 http://www.lydsy.com/JudgeOnline/problem.php? ...
-
Bzoj 2456: mode 数论,众数
2456: mode Time Limit: 1 Sec Memory Limit: 1 MBSubmit: 2843 Solved: 1202[Submit][Status][Discuss] ...
-
[POJ] 2456 Aggressive cows (二分查找)
题目地址:http://poj.org/problem?id=2456 最大化最小值问题.二分牛之间的间距,然后验证. #include<cstdio> #include<iostr ...
-
poj 2456 Aggressive cows &;&; nyoj 疯牛 最大化最小值 二分
poj 2456 Aggressive cows && nyoj 疯牛 最大化最小值 二分 题目链接: nyoj : http://acm.nyist.net/JudgeOnline/ ...
-
BZOJ 2456: mode(新生必做的水题)
2456: mode Time Limit: 1 Sec Memory Limit: 1 MB Submit: 4868 Solved: 2039 [Submit][Status][Discuss ...
-
POJ 2456 3258 3273 3104 3045(二分搜索-最大化最小值)
POJ 2456 题意 农夫约翰有N间牛舍排在一条直线上,第i号牛舍在xi的位置,其中有C头牛对牛舍不满意,因此经常相互攻击.需要将这C头牛放在离其他牛尽可能远的牛舍,也就是求最大化最近两头牛之间的距 ...
随机推荐
-
C#通过ODBC查询HANA数据库数据
创建HANA的ODBC数据库连接. 默认在控制面板——>管理工具——>数据源(ODBC) 提示:如果系统是64位的,要运行 C:\Windows\SysWOW64\odbcad32.exe ...
-
Matlab GUI设计中的一些常用函数
Matlab GUI常用函数总结 % — 文件的打开.读取和关闭% — 文件的保存% — 创建一个进度条% — 在名为display的axes显示图像,然后关闭% — 把数字转化为时间格式% — ch ...
-
Java SE 第二十三讲----static关键字and final关键字
1.static关键字 [在二十二讲视频中30分钟开始讲授] 2.static修饰属性:无论一个类生成了多少个对象,所有这些对象共同使用唯一一份静态的成员变量:一个对象对该静态成员变量进行了修改,其他 ...
-
Android自定义窗口动画
第一步,设置出现和消失的xml 1.在res/anim下创建enter_anim.xml,设置窗口出现的动画 <?xml version="1.0" encoding=&qu ...
-
HDU 4422 The Little Girl who Picks Mushrooms ( 模拟)
Problem Description It's yet another festival season in Gensokyo. Little girl Alice planned to pick ...
-
转:Validation of viewstate MAC failed异常的原因及解决方法
ViewState是一种机制,ASP.NET 使用这种机制来跟踪服务器控件状态值,否则这些值将不作为 HTTP 窗体的一部分而回传.也就是说在页面刷新或者回传的时候控件的值将被清空,我们在aspx.c ...
-
combination sum、permutation、subset(组合和、全排列、子集)
combination sum I.permutation I.subsets I 是组合和.全排列.子集的第一种情况,给定数组中没有重复的元素. combination sum II.permut ...
-
Django --- Django下载和APP创建 ORM (大概步骤)
1,下载: 命令行: pip install django == 1.11.15 pip install -i或 源 django == 1.11.15 pycharm settings 解释器 点 ...
-
第二章01:Hello world 案例
java程序开发 = 三部曲 源文件+编译器+字节码文件+解释器=结果 源文件:编写Java源文件(我们也称之为源代码文件),它的扩展名为.java: 编译:然后通过编译器把源文件编译成字节码文件,字 ...
-
使用百度ocr接口识别验证码
#!/usr/bin/env python #created by Baird from aip import AipOcr def GetCaptchaV(filename): APP_ID = ' ...