链接：https://ac.nowcoder.com/acm/problem/214362
来源：牛客网

题目描述

有一个长度为n的数组，值为 a[i], 牛牛想找到数组中第 k 小的数。比如 1 2 2 3 4  6 中，第 3 小的数就是2.
牛牛觉得这个游戏太简单了，想加一点难度，现在牛牛有 m 个操作，每个操作有两种类型。
1 x  1 代表操作一，给数组中加一个元素 x 。(0 ≤ x ≤ 1e9)
2     2 代表操作二，查询第 k 小的数。如果没有 k 个数就输出−1

输入描述: 

		

			第一行有三个整数，n m k,(1≤n,m,k≤2e5)
		


		

			第二行包含 n 个整数 a[i] ( 0 ≤ a[i] ≤ 1e9)
		


		

			接下来m行，每行代表一个操作。具体见题目描述

输出描述: 

		

			每次查询输出一个第  k  小的数。
思路：这一题的难点在于如何快速查找出第k小的数。
第一种最常见的想法是用sort来做，但是我测试了一下，会TLE
下面是TLE的代码，通过率为73.33%
#include<stdio.h>
#include<bits/stdc++.h>
#define ll long long int
ll a[500020]; 
using namespace std;
int main(){
    int n,m,k,i,t;
    scanf("%d %d %d",&n,&m,&k);
    for(i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    sort(a+1,a+1+n);
    while(m--){
        scanf("%d",&t);
        if(t==1){
            ll tmp;
            scanf("%lld",&tmp);
            n++;
            a[n]=tmp;
            sort(a+1,a+n+1);
        }else{
            if(n<k) printf("-1\n");
            else printf("%lld\n",a[k]);
        }
    }
    return 0;
}
不知道用快读函数能不能卡在1s之内完成......但是就算能卡也比较极限了吧，没试过
第二种想法（标准解法）：用小/大顶堆来做（priority_queue）
思想其实和下面这一题类似：


就是变成了求第k个小的数-->一直将第k个小的数放在大/小顶堆的顶部，方便快速取用。下面的代码是将其放在了小顶堆的顶部
注：priority_queue<int,vector<int>,greater<int>>创建的是小顶堆，priority_queue<int>创建的是大顶堆，不要记反了。
分析一下过程
先输入n个数，因为要求的是第k小数，所以相当于将第1,2,......,k-1个数放进大顶堆，第k,k+1,......,n个数放进小顶堆，这样才能通过小顶堆的顶部取到第k个小的数。
（这里有一种情况，就是n<k,那么就把全部的数放进大顶堆，本质上和上面一样）
然后如果要添加一个数a，有二类情况
一类是目前所有元素的个数还<k，此时如果这个元素是第k-1个或者更少，就将其加到大顶堆里（因为加到小顶堆里相当于第k小的数已经有了，不符合逻辑）
另一类是目前所有元素的个数已经>=k了，这里又分为2种情况
一种是a<大顶堆的顶部，那么相当于比k小的数多了一个-->将这个数放进大顶堆，然后取出大顶堆的顶部的值并放到小顶堆里面（注意top()取出后用pop()!），确保能通过小顶堆的顶部取到第k个小的数
另一种是a>=大顶堆的顶部，那么相当于比k小的数没有变-->将这个数放进小顶堆即可
最后考虑-1的情况，即为xiao.empty()为1（小顶堆为空）时输出-1
基本思路分析完成

下面是AC代码
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
int a[200020];
int main() {
    int n,m,k,i,t;
    scanf("%d %d %d",&n,&m,&k);
    priority_queue<int>da;
    priority_queue<int,vector<int>,greater<int>>xiao;
    for(i=1; i<=n; i++) {
        scanf("%d",&a[i]);
    }
    sort(a+1,a+1+n);
    for(i=1; i<=n; i++) {
        if(i<k) {
            da.push(a[i]);
        } else {
            xiao.push(a[i]);
        }
    }
    while(m--) {
        scanf("%d",&i);
        if(i==1) {
            scanf("%d",&t);
            if(n<k-1) {
                da.push(t);
                n++;
            } else {
                if(t>=da.top()) {
                    xiao.push(t);
                } else {
                    da.push(t);
                    int tmp=da.top();
                    da.pop();
                    xiao.push(tmp);
                }
            }
        } else {
            if(xiao.empty()) printf("-1\n");
            else printf("%d\n",xiao.top());
        }
    }
    return 0;
}
P.S：今天是学并查集的第二天，开心Ciallo～(∠・ω< )⌒☆