Problem Description
还记得Gardon给小希布置的那个作业么?(上次比赛的1005)其实小希已经找回了原来的那张数表,现在她想确认一下她的答案是否正确,但是整个的答案是很庞大的表,小希只想让你把答案中最大的M个数告诉她就可以了。
给定一个包含N(N<=3000)个正整数的序列,每个数不超过5000,对它们两两相加得到的N*(N-1)/2个和,求出其中前M大的数(M<=1000)并按从大到小的顺序排列。
Input
输入可能包含多组数据,其中每组数据包括两行:
第一行两个数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
堆排序:
堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值,即A[PARENT[i]] >= A[i]。在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的要求可知,最大的值一定在堆顶。
解题思路:
这题是一个求集合中前多少名的问题,算是一个比较常用的算法,一般用堆排序解即可。但是本题有一个特点是每个数不超过5000,所以最大值也就是10000,因此可以通过数组来存储。对于任意的一个和x(x<10000),我们定义sum[x],如果sum[x]大于0,则表示有x,并且有sum[x]个。
从sum的末尾开始倒数,就是所需的序列。
扩展题(面试题):
请问如何从10亿数据中取最大的100个数据?
思路:依然是采用堆排序。但是注意10亿个数据比较大,占用内存太多,因此可以限定堆的大小为100,每次输入一个新元素时,更新堆结构,使得堆结构始终存放着最大的100个数据。
源代码:G++ 15ms
#include <stdio.h>
int main()
{
//正整数序列
int set[5050];
//记录某个和所在位置的个数
int sum[10050];
int n, m;
while(~scanf("%d%d", &n, &m)){
for(int i=0; i<n;++i){
scanf("%d", &set[i]);
}
//记录和的最大值
int max = 0;
for(int i=0; i<n; ++i){
for(int j=i+1; j<n && i!=j; ++j){
//两两相加
int x = set[i] + set[j];
//更新max
if (x > max) {
max = x;
}
sum[x]++;
}
}
//从max下标开始倒数
for(int i= max, cnt=0; cnt<m; --i){
//可能有多个
while(sum[i]-- && cnt < m){
if(cnt++ == 0){
printf("%d", i);
}else{
printf(" %d", i);
}
}
}
printf("\n");
}
}