cogs 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

明显这是一道卡内存的题，苦思冥想好长时间，超内存：

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<string>
 6 #include<cstdio>
 7 #define ll long long
 8 
 9 using namespace std;
10 const int N=1500000;
11 
12 struct node{
13     int js;
14     int me;
15 }E[N];
16 int tot;
17 bool vis[N];
18 int a[N];
19 inline void read(ll &x)
20 {
21     char c=getchar();
22     x=0;
23     while(c<'0'||c>'9')c=getchar();
24     while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
25 }
26 
27 int main()
28 {
29     freopen("hztp.in","r",stdin);
30     freopen("hztp.out","w",stdout);
31     ll n;
32     read(n);
33     for(int i=1;i<=n;i++)
34     {
35         ll z;
36         read(z);
37         if(!vis[z])
38         {
39             E[++tot].me=z;
40             E[tot].js++;
41             vis[z]=1;
42         }
43         else 
44         {
45             bool _=1;
46             for(int j=1;j<=tot&&_;j++)
47             {
48                 if(E[j].me==z)
49                 {
50                     E[j].js++;
51                     _=0;
52                 }
53             }
54         }
55     }    
56     for(int i=1;i<=tot;i++)
57     {
58         if(E[i].js>=(n>>1))
59         {
60             printf("%d",E[i].me);
61             return 0;
62         }
63     }
64 }

View Code

按照下面代码自行模拟一下，还可以理解，若两数不相同则双方都可以视为不存在，这样不影响超过％50得数的存在：

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<iostream>
 4 
 5 using namespace std;
 6 
 7 int n,x,y,p;
 8 
 9 inline void read(int &x)
10 {
11     char c=getchar();
12     x=0;
13     while(c<'0'||c>'9')c=getchar();
14     while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
15 }
16 
17 int main() 
18 {
19     freopen("hztp.in","r",stdin);
20     freopen("hztp.out","w",stdout);
21     read(n);
22     for(int i=1; i<=n; i++) 
23     {
24         read(p);
25         if(y==0) 
26         {
27             x=p;
28             y++;
29         } 
30         else 
31         {
32             if(p==x) 
33                 y++;
34             else 
35                 y--;
36         }
37     }
38     printf("%d",x);
39 }