C# · 12月 20, 2021

数据结构实验之排序四:寻找大富翁

堆排序:

堆排序利用了一维数组,思想简单但是现在还是不太熟练

先把前m个人排好之后,再排后面的!

 

 

数据结构实验之排序四:寻找大富翁

Time Limit: 200 ms Memory Limit: 512 KiB

Submit Statistic

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

请用堆排序完成

#include

using namespace std;

int a[1000001];

void Cre_Heap(int a[],int i,int m)

{

int t,q;

t = i;

while(2 * i <= m)

{

if(a[t] < a[2 * i])

{

t = 2 * i;

}

if(a[t] < a[2 * i + 1] && 2 * i + 1 <= m)

{

t = 2 * i + 1;

}

if(t != i)

{

q = a[t];

a[t] = a[i];

a[i] = q;

i = t;

}

else

{

break;

}

}

}

void Jus_Heap(int a[],int m)

{

int t;

while(m >= 1)

{

t = a[m];

a[m] = a[1];

a[1] = t;

m–;

Cre_Heap(a,1,m);

}

}

int main(void)

{

int n,m,i,x;

scanf(“%d %d”,&n,&m);

for(i = 1; i <= m; i++)

{

scanf(“%d”,&a[i]);

}

for(i = m / 2; i >= 1; i–)

{

Cre_Heap(a,m);

}

Jus_Heap(a,m);

for(i = m + 1; i <= n; i++)

{

scanf(“%d”,&x);

if(a[1] < x)

{

a[1] = x;

Cre_Heap(a,m);

Jus_Heap(a,m);

}

}

for(i = m; i >= 1; i–)

{

printf(“%d%c”,a[i],i == 1 ?’n’:’ ‘);

}

return 0;

}