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

￡神魔★判官ぃ 2022-04-08 14:54 146阅读 0赞

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

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

请用堆排序完成。

Source

xam

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <math.h>
    int a[1000001];
    void swap(int *x,int *y)
    {
        int temp;
        temp=*x;
        *x=*y;
        *y=temp;
    }
    int main()
    {
        int n, m, x;
        int i, j;
        scanf("%d%d",&n, &m);
        for(i = 0; i < n; i++)
        {
            scanf("%d",&x);
            if(x > a[0])
            {
                a[0] = x;
                for(j = 0; j < m-1; j++)
                    if(a[j] > a[j+1])
                    {
                       swap(&a[j], &a[j+1]);
                    }
                    else break;
            }
        }
        for(i = m - 1; i >= 0; i--)
            printf(i==0?"%d\n":"%d ",a[i]);
        return 0;
    }

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2586/pid/3401.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2586/pid/3401.html