TZOJ 4671：求前M大的数

4671: 求前M大的数

时间限制(普通/Java):2000MS/20000MS 内存限制:65536KByte

描述

给定N个整数，求出前M大的数，并按照从小大到的顺序排序。

输入

第一行为两个正整数N和M（1<=N<=10000000, 1<=M<=10），第二行为N个非负整数。

输出

按照从小大到的顺序输出前M个整数，用空格隔开。

样例输入

5 3
3 1 2 5 4

样例输出

3 4 5

提示

由于数据量很大，请在输入数据时编写并调用以下函数读取一个非负整数：

//函数定义

int get() {
int r=0;
char c;
while(c=getchar(),!(c>=‘0’&&c<=‘9’));
r = c-‘0’;
while(c=getchar(),c>=‘0’&&c<=‘9’)
r = (r*10)+c-‘0’;
return r;
}

//读取一个整数示例

int n = get();

题目链接：http://tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=4671

题解

第一眼看到这题首先想到的是排序，但是数据太大排序肯定会TLE。只能在输入的时候判断书不是前M大的数。仔细一想可以使用优先队列完成判断，每次于对列中最小的数比较，如果大就最小数出列，当前数入列。

代码

#include<bits/stdc++.h>
using namespace std;
int get() {
    int r=0;char c;while(c=getchar(),!(c>='0'&&c<='9'));r = c-'0';while(c=getchar(),c>='0'&&c<='9')r = (r*10)+c-'0';return r;
}
priority_queue<int, vector<int>, greater<int> >qi2;
int main()
{
    int n=get();int m=get();int t;for(int i=0;i<m;++i){
    qi2.push(get());}n=n-m;for(int i=0;i<n;++i){
    t=get();if(qi2.top()>t)continue;if(t>qi2.top()){
    qi2.pop();qi2.push(t);}}t=qi2.top();printf("%d",t);qi2.pop();while(!qi2.empty()){
    printf(" %d",qi2.top());qi2.pop();}printf("\n");
}