传送门:Ignatius and the Princess IV
题意:给n个数,找出出现次数大于等于(n+1)/2的那个数。
分析:大水题,排个序输出中间那个即可,这里随便写个HASHMAP找出次数最大那个。
#include <algorithm>
#include <cstdio>
#include <cstring>
#define N 1000010
#define inf 0x3f3f3f3f
using namespace std;
const int HASH=;
const int MAXN=;
struct HASHMAP
{
int head[HASH],next[MAXN],size;
int state[MAXN],num[MAXN];
void init()
{
size=;
memset(head,-,sizeof(head));
memset(num,,sizeof(num));
}
int insert(int val)
{
int h=(val%HASH+HASH)%HASH;
for(int i=head[h];~i;i=next[i])
{
if(val==state[i])
{
num[i]++;
return num[i];
}
}
state[size]=val;
num[size]=;
next[size]=head[h];
head[h]=size++;
return ;
}
}H;
int main()
{
int n,x;
while(scanf("%d",&n)>)
{
H.init();
int mx=,ans=;
for(int i=;i<=n;i++)
{
scanf("%d",&x);
int res=H.insert(x);
if(res>mx)
{
ans=x;mx=res;
}
}
printf("%d\n",ans);
}
}