2021秋季《数据结构》_EOJ 1074. 寻找EMB富豪

题目

胡润百富是追踪记录中国企业家群体变化的权威机构，是由出生于欧洲卢森堡的英国注册会计师胡润先生于1999年创立的。是中国推出第一份财富排行榜，也是现在国内财经榜单里影响最大的一个榜单。

1999年，胡润首创“百富榜”，此后编制了一系列具有突破性意义的排行榜。旗下拥有《胡润百富》杂志，及系列论坛和活动。2004年首创“胡润慈善榜”，慈善募捐已连续发布了十年，它旨在倡导企业家们关注慈善，积极回报社会。

不可否认，富豪榜确实是胡润的一个研究产品，而且通过这个产品也使胡润成为了千万富翁。但是，富豪榜的积极意义远不止此。

首先，胡润富豪榜从富人的角度反映了中国社会的发展与进步。

其次，胡润富豪榜成了国人了解中国富豪的一扇窗口。

其三，为国人树立致富的榜样。榜样的力量是无穷的。胡润富豪榜不仅让人们认识了中国的富豪们，同时也为国人树立了致富的榜样。

类似的，EOJ研究院也公布了EMB富豪榜，以此激励同学们刷更多的EOJ题（逃

思路

堆排序，只需要对前m个（n<m则为前n个）数据进行排序即可，以m为例，

• 读入m个数据；
• 对前m个数据建立小根堆；
• 从第m+1个数据（记为val）起，检查val是否大于堆顶元素a[0]；
  • 如果大于，则将a[0]替换为val，进行一次siftdown。
    由此我们可以发现建立小根堆的理由：保证每次被换出去的数据（堆顶）都是不需要的数据。如果建立大根堆，换出去堆顶就达不到我们想要的目的，而实现换出去小元素会更加麻烦。
• 对最终获得的小根堆进行堆排序，得到的新数组为降序数组，直接输出即可。

对n<m的情况特殊讨论。

代码

#include<bits/stdc++.h>
using namespace std;int a[200001] = {
     0 };void siftdown(int a[], int i, int n)
// 调整以a[i]为根的二叉树使之成为小根堆
// 每次替换走堆顶的最小元素，保证新加入的元素为更大的元素
// 若建立大根堆，不可以替换走堆顶（最大），替换走最小元素更麻烦
{
    int j;int tmp = a[i];while ((j=2*i+1)<n){
    if (j < n - 1 && a[j + 1] < a[j])j++;if (tmp > a[j])  // 需要调整{
    a[i] = a[j];i = j;}else break;}a[i] = tmp;
}void buildHeap(int a[], int n)
{
    for (int i = (n - 2) / 2; i >= 0; i--)siftdown(a, i, n);
}void heapSort(int a[], int n)
// a已经是小根堆，排序结束后变成大根堆
{
    if (n == 0)return;// buildHeap(a, n);for (int i = n - 1; i >= 1; i--){
    int tmp = a[0];a[0] = a[i];a[i] = tmp;siftdown(a, 0, i);}
}int main()
{
    int n, m;scanf("%d %d", &n, &m);for (int i = 0; i < n; i++){
    int val;scanf("%d", &val);if (i < m)a[i] = val;else{
    if(i==m)buildHeap(a, m);// 如果val大于堆顶，则需要加入if (a[0] < val){
    a[0] = val;siftdown(a, 0, m);}}}if (n <= m)  // 此时数组并未经过排序{
    buildHeap(a, n);heapSort(a, n);for (int i = 0; i < n; i++)printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');}else{
    heapSort(a, m);for (int i = 0; i < m; i++)printf("%d%c", a[i], i == m - 1 ? '\n' : ' ');}return 0;
}