COGS 2199. [HZOI 2016] 活动投票

2199. [HZOI 2016] 活动投票

★★ 输入文件：hztp.in 输出文件：hztp.out 简单对比
时间限制：0.5 s 内存限制：2 MB

【题目描述】

衡中活动很多，人也很多，一次活动有n个学生参与投票，现已知一名参赛选手票数超过半数，求其参赛号（参赛号随机)

【输入格式】

第一行一个整数n

第二行n个整数Ni 代表第i个学生所投选手的参赛号

【输出格式】

超过半数选手的参赛号

【样例输入】

5 1 2 5 5 2 3 5 5 5

【样例输出】

【提示】

100%的数据中：n ≤3000000，1 ≤ Ni ≤300000000；

【来源】

HZOI 2016

内存2MB，完全懵了，本来想用桶来着，内存虽然2MB，那数据（指Ni，参赛号）应该也不大吧，结果参赛号随机。。

正解：思路很有意思（虽然几行代码，但第一次见，长见识了）

 1 #include<cstdio>
 2 int n,m,ans,p;
 3 int main()
 4 {
 5     freopen("hztp.in","r",stdin);
 6     freopen("hztp.out","w",stdout);
 7     scanf("%d",&n);
 8     while(n--)
 9     {
10         scanf("%d",&m);
11         if(p==0) ans = m, p++;
12         else
13             if(m==ans) p++;
14             else p--;
15     }
16     printf("%d",ans);
17 }