HDU4006 The kth great number————栈和队列（优先队列）

╰半夏微凉° 2022-05-18 01:43 178阅读 0赞

Xiao Ming and Xiao Bao are playing a simple Numbers game. In a round Xiao Ming can choose to write down a number, or ask Xiao Bao what the kth great number is. Because the number written by Xiao Ming is too much, Xiao Bao is feeling giddy. Now, try to help Xiao Bao.  
**Input**  
There are several test cases. For each test case, the first line of input contains two positive integer n, k. Then n lines follow. If Xiao Ming choose to write down a number, there will be an ” I” followed by a number that Xiao Ming will write down. If Xiao Ming choose to ask Xiao Bao, there will be a “Q”, then you need to output the kth great number.  
**Output**  
The output consists of one integer representing the largest number of islands that all lie on one line.  
**Sample Input**  
8 3  
I 1  
I 2  
I 3  
Q  
I 5  
Q  
I 4  
Q  
**Sample Output**  
1  
2  
3

**Hint**  
Xiao Ming won’t ask Xiao Bao the kth great number when the number of the written number is smaller thank.(1=<k<=n<=1000000).  k . ( 1 =< k <= n <= 1000000 ) .

--------------------

题意:  
给你一些数字，问这些数字中，第k大的数字是谁  
第一行n和k  
n代表n个操作，I表示给你数字，Q 就是让你输出给你的这些数字中第k大的是几  
下边n行，有n个操作

--------------------

思路:  
这道题用数组模拟和用map都不能过，总是TLE  
最后用优先队列才过，优先队列真是强

我们让每次给的数字都存到优先队列中，队列的元素值越小，优先级越高，我们**只需要满足队列中有k个元素就行了**

队列中始终存留着最大的k个元素

--------------------

#include<cstdio>
    #include<cstring>
    #include<string>
    #include<queue>
    #include<iostream> 
    #include<map>
    #include<vector>
    #include<stack>
    #include<algorithm>
    using namespace std;
    typedef long long ll;
    
    int main()
    {
        ios::sync_with_stdio(false);
        int n,k;
        while(cin>>n>>k)
        {
            priority_queue<int,vector<int>, greater<int> > q;
            map<int ,int > m;
            char c;
            int z=0;
            for(int i=0;i<n;i++)
            {
                cin>>c;
                if(c=='I')
                {
                    cin>>z;
                    q.push(z);
                    while(q.size()>k) q.pop();
                }
                else//询问第k大的数 
                    cout<<q.top()<<endl;
            }
        }
        return 0;
    }