首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >前m大的数(堆)- HDU 1280

前m大的数(堆)- HDU 1280

作者头像
ACM算法日常
发布2018-08-07 18:43:37
6180
发布2018-08-07 18:43:37
举报
文章被收录于专栏:ACM算法日常ACM算法日常

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");
    }
}
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2018-03-06,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 ACM算法日常 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档