首页 > 代码库 > hdu---(1280)前m大的数(计数排序)
hdu---(1280)前m大的数(计数排序)
前m大的数
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 10633 Accepted Submission(s): 3707
Problem Description
还记得Gardon给小希布置的那个作业么?(上次比赛的1005)其实小希已经找回了原来的那张数表,现在她想确认一下她的答案是否正确,但是整个的答案是很庞大的表,小希只想让你把答案中最大的M个数告诉她就可以了。
给定一个包含N(N<=3000)个正整数的序列,每个数不超过5000,对它们两两相加得到的N*(N-1)/2个和,求出其中前M大的数(M<=1000)并按从大到小的顺序排列。
给定一个包含N(N<=3000)个正整数的序列,每个数不超过5000,对它们两两相加得到的N*(N-1)/2个和,求出其中前M大的数(M<=1000)并按从大到小的顺序排列。
Input
输入可能包含多组数据,其中每组数据包括两行:
第一行两个数N和M,
第二行N个数,表示该序列。
第一行两个数N和M,
第二行N个数,表示该序列。
Output
对于输入的每组数据,输出M个数,表示结果。输出应当按照从大到小的顺序排列。
Sample Input
4 41 2 3 44 55 3 6 4
Sample Output
7 6 5 511 10 9 9 8
Author
Gardon
Source
杭电ACM集训队训练赛(VI)
计数排序是一种算法复杂度 O(n) 的排序方法,适合于小范围集合的排序。
适合在已经知道的数据范围。 这里已经知道了最大范围为:<=10000 ; 所以可以采用计数排序计算
关于计数排序的一段金典代码:
public static void Sort(int[] A, out int[] B, int k) { Debug.Assert(k > 0); Debug.Assert(A != null); int[] C = new int[k + 1]; B = new int[A.Length]; for (int j = 0; j < A.Length; j++) { C[A[j]]++; } for (int i = 1; i <= k; i++) { C[i] += C[i-1]; } for (int j = A.Length - 1; j >= 0; j--) { B[C[A[j]]-1] = A[j]; C[A[j]]--; } }
代码:
#include<stdio.h>#include<string.h>#include<stdlib.h>int main(){ int n,m,i,j,mac; //system("call test.in"); //freopen("test.in","r",stdin); while(scanf("%d%d",&n,&m)!=EOF){ int * aa= (int *)malloc(sizeof(int)*n); for(mac=i=0;i<n;i++){ scanf("%d",aa+i); if(mac<aa[i])mac=aa[i]; } int *cc =(int *)malloc(sizeof(int)*(mac*2+1)); for(i=0;i<=mac*2;i++)cc[i]=0; for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) cc[aa[i]+aa[j]]++; free(aa); for(i=mac*2;i>=0;i--){ while(cc[i]){ if(m==1) printf("%d\n",i); else printf("%d ",i); cc[i]--; m--; if(m==0)goto loop; } } loop: free(cc); } return 0;}
hdu---(1280)前m大的数(计数排序)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。