7-38 寻找大富翁 (25 分)
胡润研究院的调查显示，截至2017年底，中国个人资产超过1亿元的高净值人群达15万人。假设给出N个人的个人资产值，请快速找出资产排前M位的大富翁。
输入格式:
输入首先给出两个正整数$N$（≤106）和$M$（≤10），其中$N$为总人数，$M$为需要找出的大富翁数；接下来一行给出$N$个人的个人资产值，以百万元为单位，为不超过长整型范围的整数。数字间以空格分隔。
输出格式:
在一行内按非递增顺序输出资产排前$M$位的大富翁的个人资产值。数字间以空格分隔，但结尾不得有多余空格。
输入样例:
输出样例:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include<iostream>
#include<queue>
#include<vector>
using namespace std;
int N, M;
int main(){
scanf("%d %d", &N, &M);
priority_queue<int, vector<int>, greater<int>> q;
for(int i = 0; i < N; i++){
int num;
scanf("%d", &num);
if(q.size() < M){
q.push(num);
}else if(q.top() < num){
q.pop();
q.push(num);
}
}
vector<int> result;
while(!q.empty()){
result.push_back(q.top());
q.pop();
}
for(int i = result.size() - 1; i >= 0; i--){
printf("%d", result[i]);
if(i != 0){
printf(" ");
}else{
printf("\n");
}
}
return 0;
}
|
