SDNU 1095.Ignatius and the Princess IV（水题）

野性酷女 2021-12-22 14:07 203阅读 0赞

### 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 which are no more than 2147483647. 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

#include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <string>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    using namespace std;
    #define ll long long
    
    int n, a[1000000+8], sign[1000000+8];
    
    int main()
    {
        while(~scanf("%d", &n))
        {
            memset(sign, 0, sizeof(sign));
            int miao, ga;
            for(int i = 0; i<n; i++)
            {
                scanf("%d", &a[i]);
                sign[a[i]]++;
                if(sign[a[i]] == (n+1)/2)
                {
                    miao = a[i];
                    ga = i;
                }
            }
            printf("%d\n", a[ga]);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/RootVount/p/10891071.html