作者:唱记_665 | 来源:互联网 | 2023-09-25 14:24
题目背景自动上次redbag用加法好好的刁难过了yyy同学以后,yyy十分愤怒.他还击给了redbag一题,但是这题他惊讶的发现自己居然也不会,所以只好找你题目描述[h1]udp2
题目背景
自动上次redbag用加法好好的刁难过了yyy同学以后,yyy十分愤怒.他还击给了redbag一题,但是这题他惊讶的发现自己居然也不会,所以只好找你
题目描述
[h1]udp2:第一题因为语言性质问题,比赛结束后将所有c/c++的程序的内存调为2.2mb后重测。[/h1]
他让redbag找众数
他还特意表示,这个众数出现次数超过了一半
一共n个数,而且保证有
n<=2000000
而且每个数<2^31-1
输入输出格式
输入格式:
第一行一个整数n
第二行n个整数
输出格式:
一行,这个众数
输入输出样例
说明
时间限制 1s
空间限制 3.5M(你没看错3.5M)
有人想水过,但我告诉你这空间是不够的
//kkksc03偷偷地说:你随便输出一个数字吧,都有1/2的几率。不过这可是乐多赛,值得不值得你看着办。所以最好想一想正解。
数学题?求重数?这不太简单了。
可是这空间为啥只给3.5M啊,这咋写?
(自拟)看了这个题后:
IQ 25的YYF怯怯说:拿个数组把出现的记录下来,看看哪个数出现次数最多。
IQ 120的WLZ无力说:排一下序,既然重数超过一半,那么中间的位置一定是重数。
IQ 250的LXL欣然的说:这还不简单以第一个数为标准,第一个数出现次数为1,下一个数若与这个数相同,则这个数的次数+1,若不相同则-1,若做标准的数次数为零,则下个数将这个替换掉,因为重数出现次数超过了一半,所以最后剩下的那个标准数,只能是重数。
WLZ的代码:
#include
using namespace std;
int a[2000001],n;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+1+n);
cout<2];
}
LXL的代码:
#include
using namespace std;
int n,flag,x,cnt,now;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
if(cnt==0)now=x,cnt++;
else
{
if(now==x)
{
cnt++;
}
else cnt--;
}
}
printf("%d",now);
}
此为个人略解,转载请标明出处:http://www.cnblogs.com/rmy020718/p/8835352.html
luogu P2397 yyy loves Maths VI (mode)