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

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

Time Limit: 150MS Memory Limit: 512KB

Submit Statistic

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

请用堆排序完成。

DQE:

因为只取前M个大值，所以从M<=10入手，利用小根堆在输入时留大弃小，只保留当前最大的M个元素，从而将小根堆大小限制在M以内，最后对该小根堆进行堆排序即可~

若遇到类似取部分值题目可参考本题思想提高算法效率。

遇到TML不要方，不停提交就可以AC了，请感谢SDUT ACM不稳定的服务器造成AC/SU=84/665的这一奇观233

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 int f[12],n,m;
 5 
 6 void tz(int l,int r)
 7 {
 8     int j=2*l;
 9     while(j<=r)
10     {
11         if(j<r && f[j+1]<f[j])//小根堆
12             j++;
13         if(f[j]<f[l])//
14         {
15             *f=f[j];
16             f[j]=f[l];
17             f[l]=*f;
18             l=j;
19             j*=2;
20         }
21         else break;
22     }
23 }
24 
25 int main()
26 {
27     while(scanf("%d %d",&n,&m)!=EOF)
28     {
29         int i;
30         for(i=1;i<=m;i++)
31             scanf("%d",f+i);
32         for(i=m/2;i>=1;i--)
33             tz(i,m);
34         for(i=m+1;i<=n;i++)
35         {
36             int k;
37             scanf("%d",&k);
38             if(k>f[1])
39             {
40                 f[1]=k;
41                 int j;
42                 for(j=m/2;j>=1;j--)
43                     tz(j,m);
44             }
45         }
46         for(i=m;i>=2;i--)
47         {
48             *f=f[1];
49             f[1]=f[i];
50             f[i]=*f;
51             tz(1,i-1);
52         }
53         for(i=1;i<=m;i++)
54             printf("%d%c",f[i],i==m?'
':' ');
55     }
56     return 0;
57 }
58 
59 /***************************************************
60 User name: ***
61 Result: Accepted
62 Take time: 148ms
63 Take Memory: 148KB
64 Submit time: 2016-12-07 19:49:02
65 ****************************************************/