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

概述本文章向大家介绍数据结构实验之排序四：寻找大富翁，主要包括数据结构实验之排序四：寻找大富翁使用实例、应用技巧、基本知识点总结和需要注意事项，具有一定的参考价值，需要的朋友可以参考一下。

堆排序：

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

先把前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;

}

总结

以上是内存溢出为你收集整理的数据结构实验之排序四：寻找大富翁全部内容，希望文章能够帮你解决数据结构实验之排序四：寻找大富翁所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。