[数据结构与算法]Ignatius and the Princess IV HDU - 1029

“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. 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 2 3 3 3
11
1 1 1 1 1 7 7 7 7 7 7
5
1 1 1 1 1
Sample Output
3
7
1
——————————————分割线————————————————————
首先，欢迎HDUOJ 诈尸 复活，以后ACMer又有丰富的题做了。
激动之余，发一篇HDU的题解博客（水题）
题意大致为：给n个数 ，找出里面的众数。
一般思路为，定义一个最小值，遍历整个数组找出统计次数最多的元素。
但我们可以玩的SAO一点，用map来做，map会直接按照键值大小升序排列，但我们需要的是value值的大小。因此可以再用vector+pair进行倒腾。

#pragma GCC optimize(2)
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
#define Buff std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define int long long
using namespace std;
int n;
typedef pair<int, int> PII;
bool cmp(PII a, PII b)
{
  return a.second < b.second;
}
signed main()
{
  Buff;
  while (cin >> n)
  {
    map<int, int> mp;
    vector<PII> arr;
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
      int x;
      cin >> x;
      mp[x]++;
    }
    for (auto it = mp.begin(); it != mp.end(); it++)
    {
      arr.push_back(make_pair(it->first, it->second));
    }
    sort(arr.begin(), arr.end(), cmp);
    auto t = arr.end()-1;//敲黑板！，容器的end为虚拟结尾需要减一
    cout << t->first << endl;//输出键值
  }
  return 0;
}