2456: mode

时间:2022-12-15 09:26:52

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

5
3 2 3 1 3

Sample Output

3

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的更多相关文章

  1. BZOJ 2456 杂题 卡内存

    2456: mode Time Limit: 1 Sec  Memory Limit: 1 MBSubmit: 3702  Solved: 1551[Submit][Status][Discuss] ...

  2. POJ 2456 &lpar;二分&rpar;

    题目链接: http://poj.org/problem?id=2456 题目大意:n个房子,m头牛,房子有一个横坐标,问将m头牛塞进房子,每两头牛之间的最大间隔是多少. 解题思路: 不难看出应该二分 ...

  3. 【BZOJ】2456&colon; mode

    http://www.lydsy.com/JudgeOnline/problem.php?id=2456 题意:给一个$n<=500000$的数列,求出现次数超过$\lfloor \frac{n ...

  4. BZOJ 2456&colon; mode 水题

    2456: mode Time Limit: 1 Sec Memory Limit: 256 MB 题目连接 http://www.lydsy.com/JudgeOnline/problem.php? ...

  5. Bzoj 2456&colon; mode 数论&comma;众数

    2456: mode Time Limit: 1 Sec  Memory Limit: 1 MBSubmit: 2843  Solved: 1202[Submit][Status][Discuss] ...

  6. &lbrack;POJ&rsqb; 2456 Aggressive cows &lpar;二分查找&rpar;

    题目地址:http://poj.org/problem?id=2456 最大化最小值问题.二分牛之间的间距,然后验证. #include<cstdio> #include<iostr ...

  7. poj 2456 Aggressive cows &amp&semi;&amp&semi; nyoj 疯牛 最大化最小值 二分

    poj 2456 Aggressive cows && nyoj 疯牛 最大化最小值 二分 题目链接: nyoj : http://acm.nyist.net/JudgeOnline/ ...

  8. BZOJ 2456&colon; mode&lpar;新生必做的水题&rpar;

    2456: mode Time Limit: 1 Sec  Memory Limit: 1 MB Submit: 4868  Solved: 2039 [Submit][Status][Discuss ...

  9. POJ 2456 3258 3273 3104 3045&lpar;二分搜索-最大化最小值&rpar;

    POJ 2456 题意 农夫约翰有N间牛舍排在一条直线上,第i号牛舍在xi的位置,其中有C头牛对牛舍不满意,因此经常相互攻击.需要将这C头牛放在离其他牛尽可能远的牛舍,也就是求最大化最近两头牛之间的距 ...

随机推荐

  1. C&num;通过ODBC查询HANA数据库数据

    创建HANA的ODBC数据库连接. 默认在控制面板——>管理工具——>数据源(ODBC) 提示:如果系统是64位的,要运行 C:\Windows\SysWOW64\odbcad32.exe ...

  2. Matlab GUI设计中的一些常用函数

    Matlab GUI常用函数总结 % — 文件的打开.读取和关闭% — 文件的保存% — 创建一个进度条% — 在名为display的axes显示图像,然后关闭% — 把数字转化为时间格式% — ch ...

  3. Java SE 第二十三讲----static关键字and final关键字

    1.static关键字 [在二十二讲视频中30分钟开始讲授] 2.static修饰属性:无论一个类生成了多少个对象,所有这些对象共同使用唯一一份静态的成员变量:一个对象对该静态成员变量进行了修改,其他 ...

  4. Android自定义窗口动画

    第一步,设置出现和消失的xml 1.在res/anim下创建enter_anim.xml,设置窗口出现的动画 <?xml version="1.0" encoding=&qu ...

  5. HDU 4422 The Little Girl who Picks Mushrooms ( 模拟)

    Problem Description It's yet another festival season in Gensokyo. Little girl Alice planned to pick ...

  6. 转:Validation of viewstate MAC failed异常的原因及解决方法

    ViewState是一种机制,ASP.NET 使用这种机制来跟踪服务器控件状态值,否则这些值将不作为 HTTP 窗体的一部分而回传.也就是说在页面刷新或者回传的时候控件的值将被清空,我们在aspx.c ...

  7. combination sum、permutation、subset&lpar;组合和、全排列、子集&rpar;

    combination sum I.permutation I.subsets  I 是组合和.全排列.子集的第一种情况,给定数组中没有重复的元素. combination sum II.permut ...

  8. Django --- Django下载和APP创建 ORM &lpar;大概步骤&rpar;

    1,下载: 命令行: pip install django == 1.11.15 pip install -i或 源 django == 1.11.15 pycharm settings 解释器 点 ...

  9. 第二章01:Hello world 案例

    java程序开发 = 三部曲 源文件+编译器+字节码文件+解释器=结果 源文件:编写Java源文件(我们也称之为源代码文件),它的扩展名为.java: 编译:然后通过编译器把源文件编译成字节码文件,字 ...

  10. 使用百度ocr接口识别验证码

    #!/usr/bin/env python #created by Baird from aip import AipOcr def GetCaptchaV(filename): APP_ID = ' ...