首页 > 代码库 > BJFU 1068
BJFU 1068
描述
某次科研调查时得到了n个自然数,每个数均不超过1500000000(1.5*109)。已知不相同的数不超过10000个,现在需要统计这些自然数各自出现的次数,并按照自然数从小到大的顺序输出统计结果。
输入
包含n+1行:
第1行是整数n(1<=n<=200000),表示自然数的个数。
第2~n+1行每行一个自然数。
输出
包含m行(m为n个自然数中不相同数的个数),按照自然数从小到大的顺序输出。每行输出两个整数,分别是自然数和该数出现的次数,其间用一个空格隔开。
样例输入
8
2
4
2
4
5
100
2
100
样例输出
2 3
4 2
5 1
100 2
题目来源
090824210
快排吧直接,计数用二维数组实现。↓
1 #include <stdio.h> 2 3 void soort(long* a,long left,long right); 4 int main() 5 { 6 long n,i,j; 7 while(scanf("%ld",&n)!=EOF) 8 { 9 long ret[200000]={0}; 10 for(i=0;i<n;i++) scanf("%ld",&ret[i]); 11 soort(ret,0,n-1); 12 long sum[10000][2]={0}; 13 sum[0][0]=ret[0]; 14 sum[0][1]=1; 15 for(i=1,j=0;i<n;i++) 16 { 17 if(ret[i]==ret[i-1]) sum[j][1]++; 18 else 19 { 20 sum[++j][0]=ret[i]; 21 sum[j][1]++; 22 } 23 } 24 for(i=0;i<10000;i++) if(sum[i][1]) printf("%ld %ld\n",sum[i][0],sum[i][1]); 25 } 26 return 0; 27 } 28 void soort(long* a,long left,long right) 29 { 30 if(left>=right) return; 31 long temp; 32 long i = left; 33 long j = right; 34 long key = a[left]; 35 while(i<j) 36 { 37 while(i<j&&key<=a[j]) j--; 38 temp = a[i]; 39 a[i]=a[j]; 40 a[j]=temp; 41 while(i<j&&key>=a[i]) i++; 42 temp = a[i]; 43 a[i] = a[j]; 44 a[j] = temp; 45 } 46 soort(a,left,i-1); 47 soort(a,i+1,right); 48 }
BJFU 1068
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。