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

逃离我推掉我的手 2022-06-03 08:41 161阅读 0赞

Time Limit: 200MS Memory Limit: 512KB

#### Problem Description ####

2015胡润全球财富榜调查显示，个人资产在1000万以上的高净值人群达到200万人，假设给出N个人的个人资产值，请你快速找出排前M位的大富翁。

#### Input ####

首先输入两个正整数N( N ≤ 10^6)和M(M ≤ 10)，其中N为总人数，M为需要找出的大富翁数目，接下来给出N个人的个人资产，以万元为单位，个人资产数字为正整数，数字间以空格分隔。

#### Output ####

一行数据，按降序输出资产排前M位的大富翁的个人资产值，数字间以空格分隔，行末不得有多余空格。

#### Example Input ####

6 3
    12 6 56 23 188 60

#### Example Output ####

188 60 56

#### Hint ####

请用堆排序完成。

方法一：

#include <iostream>
    #include <cstdio>
    using namespace std;
    int f[12],n,m;
    
    void tz(int l,int r)
    {
        int j=2*l;
        while(j<=r)
        {
            if(j<r && f[j+1]<f[j])//小根堆
                j++;
            if(f[j]<f[l])//
            {
                *f=f[j];
                f[j]=f[l];
                f[l]=*f;
                l=j;
                j*=2;
            }
            else break;
        }
    }
    
    int main()
    {
        while(scanf("%d %d",&n,&m)!=EOF)
        {
            int i;
            for(i=1;i<=m;i++)
                scanf("%d",f+i);
            for(i=m/2;i>=1;i--)
                tz(i,m);
            for(i=m+1;i<=n;i++)
            {
                int k;
                scanf("%d",&k);
                if(k>f[1])
                {
                    f[1]=k;
                    int j;
                    for(j=m/2;j>=1;j--)
                        tz(j,m);
                }
            }
            for(i=m;i>=2;i--)
            {
                *f=f[1];
                f[1]=f[i];
                f[i]=*f;
                tz(1,i-1);
            }
            for(i=1;i<=m;i++)
                printf("%d%c",f[i],i==m?'\n':' ');
        }
        return 0;
    }

方法二：

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int a[30];
        int n,m,i,x;
        scanf("%d%d",&n,&m);
        for(i=0;i<m;i++)
        {
            scanf("%d",&a[i]);
        }
        sort(a,a+m);
        for(i=m;i<n;i++)
        {
            scanf("%d",&x);
            if(x>a[0])
            {
                a[0]=x;
                sort(a,a+m);
            }
    
        }
        for(i=m-1;i>=0;i--)
        {
            printf("%d%c",a[i],i==0?'\n':' ');
        }
        return 0;
    }