题解 | #第k小#

类似于求中位数，求中位数是将前一半小的数放入大顶堆，而本题可以前k小的数放入大顶堆中，因此维护大小始终为k的大顶堆即可。

对于准备插入的数

1. 如果size小于k就直接插入

2. 大于等于堆顶就跳过

3. 小于堆顶就踢出当前堆顶，插入

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) {
		InputReader in = new InputReader();
		PrintWriter out = new PrintWriter(System.out);
        PriorityQueue<Integer> p = new PriorityQueue<>();
        int n = in.nextInt();
        int m = in.nextInt();
        int k = in.nextInt();
        for(int i = 0; i < n; ++i) {
            int num = in.nextInt();
            if(p.size() < k)
                p.add(-num);
            else if(num < -p.peek()) {
                p.poll();
                p.add(-num);
            }
        }
        for(int i = 0; i < m; ++i) {
            int opr = in.nextInt();
                if(opr == 1) {
                int num = in.nextInt();
                if(p.size() < k)
                    p.add(-num);
                else if(num < -p.peek()) {
                    p.poll();
                    p.add(-num);
                }
            } else out.println(p.size() < k ? -1 : -p.peek());
        }
        
		out.close();
	}
}