题目大意：给定数字n(n <= 999999 且n为奇数 )以及n个数，找出至少出现(n+1)/2次的数
解题思路：n个数遍历过去，可以用一个map（也可以用数组）记录每个数出现的次数，
若次数一旦达到(n+1)/2，即输出a[i]
注意能出现(n+1)/2次数的最多只有一个
/* HDU 1029 *Ignatius and the Princess IV --- dp */
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std; const int maxn = ;
int a[maxn]; map<int, int> m; int main()
{
#ifdef _LOCAL
freopen("D:\\input.txt", "r", stdin);
#endif int n;
int ans;
while (scanf("%d", &n) == ){
m.clear(); //记得清空原有的东西
for (int i = ; i <= n; ++i){
scanf("%d", a + i);
++m[a[i]];
if (m[a[i]] == (n + ) / ){
ans = a[i];
}
}//for(i)
printf("%d\n", ans);
} return ;
}