Ignatius and the Princess IV【基础DP】

题目链接: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保存每个数字出现的次数,遇到正确答案后保存正确答案即可;


代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;

#define long long long
#define INF 0x3f3f3f3f
#define MAX_N 100010

int 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;
}
-------------本文结束,感谢您的阅读!-------------