题目链接：HDU-1029
kuangbin带你飞【专题十二 基础DP1 】
题目描述：
“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?
** 思路: **
感觉不是DP，单纯的统计一下每个数字出现的次数即可；
若某个出现的次数 >= (n + 1) / 2，则其就是答案;
我们用map保存每个数字出现的次数，遇到正确答案后保存正确答案即可；
代码:
#include <bits/stdc++.h>
using namespace std;#define long long long
#define INF 0x3f3f3f3f
#define MAX_N 100010int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, tmp, key;while(cin >> n){
map<int, int> F;for(int i = 1; i <= n; i++){
cin >> tmp;F[tmp]++;if(F[tmp] >= (n + 1) / 2)key = tmp;}cout << key << endl;}return 0;
}