CCF 201503-2 数字排序

  • 作者:Moilk
  • 最后编辑:2016年09月05日
  • 标签: CCF 算法

问题描述
  给定n个整数,请统计出每个整数出现的次数,按出现次数从多到少的顺序输出。
输入格式
  输入的第一行包含一个整数n,表示给定数字的个数。
  第二行包含n个整数,相邻的整数之间用一个空格分隔,表示所给定的整数。
输出格式
  输出多行,每行包含两个整数,分别表示一个给定的整数和它出现的次数。按出现次数递减的顺序输出。如果两个整数出现的次数一样多,则先输出值较小的,然后输出值较大的。
样例输入
  12
  5 2 3 3 1 3 4 2 5 2 3 5
样例输出
  3 4
  2 3
  5 3
  1 1
  4 1
评测用例规模与约定
  1 ≤ n ≤ 1000,给出的数都是不超过1000的非负整数。

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<unsigned short,unsigned short> PAIR;

map<unsigned short,unsigned short> mp;
vector<PAIR> vec;

bool cmp(PAIR a,PAIR b){
	if(a.second>b.second){
		return true;
	}
	if(a.second<b.second){
		return false;
	}
	if(a.first>b.first){
		return false;
	}
	return true;
}

int main(void){
	int N;
	unsigned short tmp;
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>tmp;
		mp[tmp]++;
	}
	for(map<unsigned short,unsigned short>::iterator it=mp.begin();it!=mp.end();it++){
		vec.push_back(*it);
	}
	sort(vec.begin(),vec.end(),cmp);
	for(vector<PAIR>::iterator it=vec.begin();it!=vec.end();it++){
		cout<<it->first<<' '<<it->second<<endl;
	}
	
	return 0;
}