Ignatius and the Princess IV

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32767 K (Java/Others)

Total Submission(s): 51503 Accepted Submission(s): 23178

Problem Description

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

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個，将該組數中相同數字的個數大于（n+1）/ 2 的數字輸出。

我是看題目分類來做這個題的，怎麼也想不出來動規怎麼做看了别人的題解恍然大悟真是太高妙了

如果這個數出現次數大于（n+1）/ 2的話那麼他比所有其他的數出現次數都要多！

具體的看代碼吧應該很清楚了

#include<bits/stdc++.h>

using namespace std;

int i,n,cnt,anss,x;

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        cnt=0;
        for(i=1;i<=n;i++)
        {
            cin>>x;
            if(cnt==0)
            {
                cnt++;
                anss=x;
            }
            else
            {
                if(x==anss)
                cnt++;
                else
                cnt--;
            }        
        }
        cout<<anss<<endl;
    }
}

HDU 1029 Ignatius and the Princess IV （動态規劃、思維）Ignatius and the Princess IV