前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 4
1 2 3 4
4 5
5 3 6 4
Sample Output
7 6 5 5
11 10 9 9 8
Author
Gardon
Source
计数排序是一种算法复杂度 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 ",i); else printf("%d ",i); cc[i]--; m--; if(m==0)goto loop; } } loop: free(cc); } return 0; }