HUD 1029 Ignatius and the Princess IV

Ignatius and the Princess IV

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32767 K (Java/Others)
Total Submission(s): 34894 Accepted Submission(s): 15238

Problem Description

“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?

Input

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.

Output

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

Sample Input

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

Sample Output

3
5
1

题意：

　　　　给你n个数，让你找出一个至少出现了(ｎ+1)/2次的数。
　　　　

思路：

　　　　至少出现了(ｎ+1)/2，已经至少是数列的一半，说明数列中最多只有一个这样的数。我们可以通过一个变量cnt来计数，如果是这个数,cnt就自增，否则就自减，如果减到零，说明这个数不是最多的那个数，则此时res的值换为这个数，再按上面的步骤继续计数判断。
　　　　

代码：

/*
*         Submit Time Judge      Status   Pro.ID    Exe.Time    Exe.Memory  Code Len.   Language
*HUD 1029 2017-09-19 20:32:25   Accepted    1029    187MS         1712K       482 B       G++
*/

#include<iostream>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n = 0;
    while (cin >> n &&n) {
        int cnt = 0, x = 0, res = 0;
        for (int i = 0; i < n; i++) {
            cin >> x;
            if (cnt == 0) {
                res = x;
                cnt++;
            }
            else if (x == res) cnt++;
            else cnt--;    
        }
        cout << res << endl;
    }
    return 0;
}





//