F - 数据结构实验之排序四:寻找大富翁
Description
2015胡润全球财富榜调查显示,个人资产在1000万以上的高净值人群达到200万人,假设给出N个人的个人资产值,请你快速找出排前M位的大富翁。
Input
首先输入两个正整数N( N ≤ 10^6)和M(M ≤ 10),其中N为总人数,M为需要找出的大富翁数目,接下来给出N个人的个人资产,以万元为单位,个人资产数字为正整数,数字间以空格分隔。
保证所有的数据大小均在int范围内。
Output
一行数据,按降序输出资产排前M位的大富翁的个人资产值,数字间以空格分隔,行末不得有多余空格。
Sample
Input
6 3 12 6 56 23 188 60
Output
188 60 56
Hint
请用堆排序完成。
#include<bits/stdc++.h> using namespace std; int a[15], n; void heapedjust(int s, int n){ //将已有的堆调整为大根堆 int t = a[s]; for(int j=2*s; j<=n; j*=2){ //从数值较大的孩子开始调整 if(j<n&&a[j]>a[j+1])j++; //记录数值较大的孩子的下标 if(t<a[j])break; //如果到了某一个孩子,数值小于堆顶,则调整完成 a[s] = a[j]; s = j; } a[s] = t; //交换调整的位置与堆顶 } void heapcreat(int n){ //创建一个大根堆,从第一个可能不是大根堆的开始,也就是n/2处 for(int i=n/2; i>=1; i--){ //一直调整到第一个位置 heapedjust(i, n); } } void heapsort(int n){ //堆排序,进行n-1次调整 for(int i=n; i>1; i--){ swap(a[1], a[i]); heapedjust(1, i-1); } } int main(){ ios::sync_with_stdio(false); int m, temp; while(cin>>n>>m){ for(int i=1; i<=m; i++){ cin>>a[i]; } heapcreat(m); for(int i=m+1; i<=n; i++){ //题目对数据的内存和时间要求较高,所以只需存储要求的m个数据 cin>>temp; //只需要对数据不断进行更新即可 if(temp<a[1]) continue; a[1] = temp; heapcreat(m); } heapsort(m); //只对m个数据进行排序 int i; for(i=1; i<=m-1; i++) cout<<a[i]<<" "; cout<<a[i]<<endl; } return 0; }