Time Limit: 200 ms Memory Limit: 512 KiB
Submit Statistic Discuss
Problem Description
2015胡润全球财富榜调查显示，个人资产在1000万以上的高净值人群达到200万人，假设给出N个人的个人资产值，请你快速找出排前M位的大富翁。
Input
首先输入两个正整数N( N ≤ 10^6)和M(M ≤ 10)，其中N为总人数，M为需要找出的大富翁数目，接下来给出N个人的个人资产，以万元为单位，个人资产数字为正整数，数字间以空格分隔。
Output
一行数据，按降序输出资产排前M位的大富翁的个人资产值，数字间以空格分隔，行末不得有多余空格。
Sample Input
6 3 12 6 56 23 188 60
Sample Output
188 60 56
Hint
请用堆排序完成。
Source
xam
一开始照着书敲的最大堆，建立最大堆再输出m个元素，出现了两个错误，一个内存将数组a[10000]扩大至a[1000000]即可解决，还有一个超时的错误本以为输入C++输入加速语句可以解决，结果还是因为规模的问题没有解决，参考了
https://blog.csdn.net/weixin_43283687/article/details/85330125的文章后按照这个思路来写可以解决超时。个人理解这一方法其实是在缩小规模，先建立一个最小堆，在对最小堆反向排序为最大堆，再输出最大堆的a[1],a[2]...a[m]即可，而非正常建立最大堆一次次维护输出。先对前m个元素建立最小堆，再加入n-m个元素，不停维护堆。继续通过一个for循环，控制堆元素数目heap_size，使得最小堆逐步变成最大堆，这儿需要理解堆排序元素输出的本质，以最小堆为例，其输出的本质是把堆顶元素与堆最后一个叶子结点的元素进行交换，交换后heap_size减一，对堆进行重新的维护，便实现了堆顶元素的输出。输出的本质便是将堆顶元素放置在最后一个叶子结点上，每一次维护都能确保最小的元素在堆顶，继而放置到最后一个叶子结点，再将叶子结点断裂（通过heap_size-1来实现）。
代码如下，还有为什么要先建立m个元素的堆仍有疑问
#include <iostream>using namespace std;int a[1000000];
int heap_size=0;void swap(int &a,int &b)
{int tmp;tmp=a;a=b;b=tmp;
}void Insert(int x)
{heap_size++;//下标由1开始计算起a[heap_size]=x;for(int i=heap_size; i!=0; i=i/2){if(a[i]<a[i/2]){swap(a[i],a[i/2]);//相当于是左右孩子结点与根结点的比较}else{break;}}
}//对于前m个元素先进行插入，省时,直接建立规模为m小顶堆,初步维护？void Adjust()
{int i,minest;for(int i=1;2*i<=heap_size;i=minest){if(2*i+1<=heap_size&&a[2*i+1]<a[2*i]){minest=2*i+1;}else{minest=2*i;}if(a[i]>a[minest]){swap(a[i],a[minest]);}else{break;}}
}//对于堆中的元素进行调整？int main()
{std::ios_base::sync_with_stdio(false);std::cin.tie(0);int n,m;cin>>n>>m;for(int i=0; i<m; i++){int x;cin>>x;Insert(x);}for(int j=m; j<n; j++){int x;cin>>x;if(x>a[1]){a[1]=x;Adjust();}}for(int l=m; l>=1; l--){swap(a[l],a[1]);//小顶堆的排序法，最后一位数于堆顶元素heap_size--;Adjust();}for(int k=1; k<=m; k++){if(k!=m){cout<<a[k]<<" ";}else if(k==m){cout<<a[k]<<endl;}}return 0;
}