数据结构实验之排序四:寻找大富翁
Time Limit: 200MS
Memory Limit: 512KB
Problem Description
2015胡润全球财富榜调查显示,个人资产在1000万以上的高净值人群达到200万人,假设给出N个人的个人资产值,请你快速找出排前M位的大富翁。
Input
首先输入两个正整数N( N ≤ 10^6)和M(M ≤ 10),其中N为总人数,M为需要找出的大富翁数目,接下来给出N个人的个人资产,以万元为单位,个人资产数字为正整数,数字间以空格分隔。
Output
一行数据,按降序输出资产排前M位的大富翁的个人资产值,数字间以空格分隔,行末不得有多余空格。
Example Input
6 3 12 6 56 23 188 60
Example Output
188 60 56
Hint
请用堆排序完成。
Author
xam
#include <stdio.h>
#define MaxN 12
int a[MaxN];
int n,m;
void heapjust(int low ,int hight)
{if(low < hight){int i,t = a[low];for(i = 2*low;i < hight;i*=2){if(i < hight&&a[i]>a[i+1])i++;if(a[low] < a[i])break;a[low] = a[i];low = i;}a[low] = t;}
}
int main()
{int t,i,j;while(scanf("%d%d",&n,&m) != EOF){for(i = 1;i <= m;i++){scanf("%d",&a[i]);}for(i = m/2;i > 0;i--){heapjust(i,m);}for(i = m+1;i <= n;i++){scanf("%d",&t);if(t<a[1])continue;a[1] = t;for(j = m/2;j>0;j--){heapjust(j,m);}}for(i = m;i>0;i--){int tmp = a[1];a[1] = a[i];a[i] = tmp;heapjust(1,i-1);}for(i = 1;i <= m;i++){printf("%d%c",a[i],i==m?'\n':' ');}}return 0;
}