首页 > ACM题库 > HDU-杭电 > HDU 1029 Ignatius and the Princess IV-线性结构-[解题报告] C++
2013
11-26

HDU 1029 Ignatius and the Princess IV-线性结构-[解题报告] C++

Ignatius and the Princess IV

问题描述 :

"OK, you are not too bad, em… But you can never pass the next test." feng5166 says.

"I will tell you an odd number N, and then N integers. There will be a special integer among them, you have to tell me which integer is the special one after I tell you all the integers." feng5166 says.

"But what is the characteristic of the special integer?" Ignatius asks.

"The integer will appear at least (N+1)/2 times. If you can’t find the right integer, I will kill the Princess, and you will be my dinner, too. Hahahaha….." feng5166 says.

Can you find the special integer for Ignatius?

输入:

The input contains several test cases. Each test case contains two lines. The first line consists of an odd integer N(1<=N<=999999) which indicate the number of the integers feng5166 will tell our hero. The second line contains the N integers. The input is terminated by the end of file.

输出:

For each test case, you have to output only one line which contains the special number you have found.

样例输入:

5
1 3 2 3 3
11
1 1 1 1 1 5 5 5 5 5 5
7
1 1 1 1 1 1 1

样例输出:

3
5
1

看题目觉得还挺奇怪的,后来反应过来其实是求一堆数字的众数。。。。

最近做题真是越来越懒了。。。= = 有木有人可以监督我唉%>_<%

1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 int main(){
 5     int n, num[50000], tem, i, j;
 6     while(scanf("%d",&n) != EOF){
 7         memset(num, 0, sizeof(num));
 8         for(i = 1; i <= n; i++){
 9             scanf("%d",&tem);
10             num[tem]++;
11             if(num[tem] >= (n + 1) / 2)
12                 j = tem;
13         }
14         printf("%d\n",j);
15     }
16     return 0;
17 }