map 键值对解决用vector转存，在用sort排序

Myth丶恋晨 2024-02-18 22:32 78阅读 0赞

## Ignatius and the Princess IV ##

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32767 K (Java/Others)  
Total Submission(s): 43163 Accepted Submission(s): 18908**

**Problem Description**

"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 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

**Author**

Ignatius.L

\#include<iostream>  
\#include<map>  
\#include<stdio.h>  
\#include<vector>  
\#include<algorithm>  
using namespace std;  
int cmp(const pair<int,int> &a,const pair<int,int> &b)  
\{  
return a.second>b.second;  
\}  
void Copy\_map\_value(vector<pair<int,int> >&a,map<int,int> &b)  
\{  
for(map<int,int>::iterator it=b.begin();it!=b.end();it++)  
\{  
a.push\_back(make\_pair(it->first,it->second));  
\}  
sort(a.begin(),a.end(),cmp);  
\}  
int main()  
\{  
map<int,int> q;  
int n,i,j,t;  
while(~scanf("%d",&n))  
\{  
for(i=0;i<n;i++)  
\{  
scanf("%d",&t);  
if(q.count(t)==1)  
\{  
q\[t\]++;  
\}  
else  
q.insert(make\_pair(t,1));  
\}  
vector<pair<int,int> >a;  
Copy\_map\_value(a,q);  
for(i=0;i<a.size();i++)  
if(a\[i\].second>=(n+1)/2)  
printf("%d\\n",a\[i\].first);  
if(!q.empty())  
q.clear();  
\}  
return 0;  
\}