问题描述

某次科研调查时得到了n个自然数，每个数均不超过1500000000 （1.5*109）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。

Input

输入文件count.in包含n+1行； 第一行是整数n，表示自然数的个数； 第2~n+1每行一个自然数。

Output

输出文件count.out包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。 【限制】

40%的数据满足：1<=n<=1000

80%的数据满足：1<=n<=50000

100%的数据满足：1<=n<=200000，每个数均不超过1500 000 000（1.5*109）

Sample Input

12
9
1400000000
3
89
5645897
6
897456322
8
8
1500000000
90
89

Sample Output

3 1
6 1
8 2
9 1
89 2
90 1
5645897 1
897456322 1
1400000000 1
1500000000 1

【题解】

用快排排一遍，相同的数字会连续出现，输出时注意下就好。

【代码】

#include

const int MAXN = 200000+10;

int n,a[MAXN];

void input_data() //输入数据
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
}

void q_sort(int l,int r) //快排
{
int m = a[(l+r)/2];
int i = l,j = r;
do
{
while (a[i] < m) i++;
while (m < a[j]) j--;
if (i <= j)
{
int t = a[i];a[i]=a[j];a[j]=t;
i++;j--;
}
} while (i<=j);
if (l < j) q_sort(l,j);
if (i < r) q_sort(i,r);
}

void get_put_ans() //输出答案
{
int i = 1;
while (i <= n)
{
int j = i+1;
while ( a[j] == a[i]) j++;
printf("%d %d\n",a[i],j-i);
i = j;
}
}

int main()
{
input_data();
q_sort(1,n);
get_put_ans();
return 0;
}