洛谷 P1138 第K小整数

题目描述

现有n个正整数，n≤10000，要求出这n个正整数中的第k个最小整数（相同大小的整数只计算一次），k≤1000，正整数均小于30000。

输入输出格式

输入格式：

第一行为n和k; 第二行开始为n个正整数的值，整数间用空格隔开。

输出格式：

第k个最小整数的值；若无解，则输出“NO RESULT”。

输入样例#1：

5
1 2
1 5
2
3
2

输出样例#1：

2
5

原题戳

用一个堆，每次读入时将其加入堆中，输出时，从堆顶移除k-1个元素，再输出堆顶元素即可

代码

//By Acer.mo
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
struct ed
{
    int a;
    bool friend operator < (ed m,ed n)
    {
        return m.a>n.a;
    }
};
bool jud[500000]={0}; 
int main()
{
    int t,i,k;
    priority_queue<ed>q;
    cin>>t>>k;
    for (i=1;i<=t;i++)
    {
        ed sum;
        cin>>sum.a;
        if (!jud[sum.a])
        {
            jud[sum.a]=1;
            q.push(sum);
        }
    }
    if (q.size()<k)
    {
        cout<<"NO RESULT";
        return 0;
    }
    while (k!=1)
    {	
        q.pop();
        k--;
    }
    ed ans=q.top();
        cout<<ans.a;
    return 0;
}