題目描述

2015胡潤全球財(cái)富榜調(diào)查顯示，個(gè)人資產(chǎn)在1000萬以上的高凈值人群達(dá)到200萬人，假設(shè)給出N個(gè)人的個(gè)人資產(chǎn)值，請你快速找出排前M位的大富翁。

輸入

首先輸入兩個(gè)正整數(shù)N( N ≤ 10^6)和M(M ≤ 10)，其中N為總?cè)藬?shù)，M為需要找出的大富翁數(shù)目，接下來給出N個(gè)人的個(gè)人資產(chǎn)，以萬元為單位，個(gè)人資產(chǎn)數(shù)字為正整數(shù)，數(shù)字間以空格分隔。

輸出

一行數(shù)據(jù)，按降序輸出資產(chǎn)排前M位的大富翁的個(gè)人資產(chǎn)值，數(shù)字間以空格分隔，行末不得有多余空格。 ?

示例輸入

6 3 12 6 56 23 188 60

示例輸出

188 60 56

提示

請用堆排序完成。?

/*#include <iostream>
#include<bits/stdc++.h>
using namespace std;


int main()
{
? ? int n,m;
? ? int a[100001];
? ? scanf("%d%d",&n,&m);
? ? for(int i=0;i<n;i++)
? ? ? ? scanf("%d",&a[i]);
? ? ? ? sort(a,a+n);
? ? ? ? int j=0;
? ? ? ? int b[100001];
? ? ? ? for(int i=n-1;i>=0;i--)
? ? ? ? {
? ? ? ? ? ? b[j]=a[i];
? ? ? ? ? ? j++;
? ? ? ? }
? ? ? ? for(int i=0;i<m-1;i++)
? ? ? ? ? ? printf("%d ",b[i]);
? ? ? ? ? ? printf("%d\n",b[m-1]);


? ? return 0;
}


解法二（快速排序）、


#include<stdio.h>
#include<stdlib.h>
int cmp(const void *a,const void *b)//比較函數(shù)；快排的升序
{
? ? return *(int *)b-*(int *)a;
}
int main()
{
? ? int i,j,n,m,k,t,l;
? ? while(scanf("%d %d",&n,&m)!=EOF)
? ? {
? ? ? ? int a[12];
? ? ? ? k=0;
? ? ? ? for(i=0;i<n;i++)
? ? ? ? {
? ? ? ? ? ? scanf("%d",&t);
? ? ? ? ? ? if(k<m)
? ? ? ? ? ? ? ? a[k++]=t;
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? l=0;
? ? ? ? ? ? ? ? for(j=1;j<k;j++)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? if(a[l]>a[j])
? ? ? ? ? ? ? ? ? ? ? ? l=j;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if(a[l]<t)//更新小的元素；
? ? ? ? ? ? ? ? ? ? a[l]=t;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? qsort(a,m,sizeof(a[0]),cmp);//快速排序；
? ? ? ? for(i=0;i<m; i++)
? ? ? ? ? ? if(i==0)
? ? ? ? ? ? ? ? printf("%d",a[i]);
? ? ? ? ? ? else
? ? ? ? ? ? ? ? printf(" %d",a[i]);
? ? ? ? printf("\n");
? ? }
}*/
#include<stdio.h>
#include <iostream>
#include<algorithm>
using namespace std;
void HeapAdjust(int *a,int i,int size)//篩選調(diào)整大頂堆的算法；
{
? ? int lchild=2*i;
? ? int rchild=2*i+1;
? ? int max=i;
? ? if(i<=size/2)
? ? {
? ? ? ? if(lchild<=size&&a[lchild]>a[max])
? ? ? ? {
? ? ? ? ? ? max=lchild;
? ? ? ? }
? ? ? ? if(rchild<=size&&a[rchild]>a[max])
? ? ? ? {
? ? ? ? ? ? max=rchild;
? ? ? ? }
? ? ? ? if(max!=i)
? ? ? ? {
? ? ? ? ? ? swap(a[i],a[max]);
? ? ? ? ? ? HeapAdjust(a,max,size);//調(diào)整為部分堆；
? ? ? ? }
? ? }
}


void BuildHeap(int *a,int size)//建堆；
{
? ? int i;
? ? for(i=size/2; i>=1; i--)
? ? {
? ? ? ? HeapAdjust(a,i,size);
? ? }
}


void HeapSort(int *a,int size)//堆排序
{
? ? int i;
? ? BuildHeap(a,size);//先建堆；
? ? for(i=size; i>=1; i--)
? ? {
? ? ? ? swap(a[1],a[i]);//交換首尾兩元素；
? ? ? ? HeapAdjust(a,1,i-1);//篩選調(diào)整為堆；
? ? }
}
int main()
{
? ? int i,j,n,m,k,t,l;
? ? while(scanf("%d %d",&n,&m)!=EOF)
? ? {
? ? ? ? int a[11];
? ? ? ? k=1;
? ? ? ? for(i=0; i<n; i++)
? ? ? ? {
? ? ? ? ? ? scanf("%d",&t);
? ? ? ? ? ? if(k<m+1)
? ? ? ? ? ? ? ? a[k++]=t;//存儲前m個(gè)元素；
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? l=1;
? ? ? ? ? ? ? ? for(j=2; j<k; j++)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? if(a[l]>a[j])//找最小的元素；
? ? ? ? ? ? ? ? ? ? ? ? l=j;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if(a[l]<t)//更新小的元素；
? ? ? ? ? ? ? ? a[l]=t;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? HeapSort(a,m);//堆排序從小到大注意是m個(gè)元素建堆。
? ? ? ? for(i=m;i>=1;i--)
? ? ? ? ? ? if(i==m)
? ? ? ? ? ? ? ? printf("%d",a[i]);
? ? ? ? ? ? else
? ? ? ? ? ? ? ? printf(" %d",a[i]);
? ? ? ? printf("\n");
? ? }
}

總結(jié)

以上是生活随笔為你收集整理的数据结构实验之排序四：寻找大富翁的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。