K优先队列-布布扣-bubuko.com

题目描述

你需要维护一个队列，支持以下两种操作：
1.加入一个非负整数x；
2.取出当前队列中第k大的数字。
保证进行第二种操作时，队列中至少有k个数字。
部分数据经过加密，你需要依次处理每个操作才能获得正确的下一个操作。

输入

第一行包括三个非负整数n,k,p，分别表示操作次数，参数k以及数据是否进行过加密。
接下来n行，每行先给出一个数opt，表示操作类型。若opt=1,接下来还会有一个非负整数x,若p=0，表示往队列中加入x，若p=1，表示往队列中加入x异或上前一次出队操作取出的数字后得到的结果，如果还未进行过出队操作，把前一次取出的数字看作0。若opt=2，表示要求取出并输出当前队列中第k大的数字。

输出

对于每一个出队操作，输出一个正整数表示答案。

样例输入

样例输出

2
1

提示

对于100%的数据，1≤k≤n≤2∗105，0≤x≤109。

题解

　　唉，太菜了。两个容器，一个容量为k的容器，存储前k大的数（实际是一个小根堆，姑且称之为容器q1），另一个容器存储没有被取出并且不在q1的数（一个大根堆，称之为容器q2）。

　　操作1：如果q1不足k个数，把新增的数插入q1。如果q1中已经有k个数了，先把新增数插入q1，然后把q1的堆顶元素插入q2，弹出q1的堆顶，保证q1中还是k个数。

　　操作2：取出q1的堆顶，用q2的堆顶（如果q2非空）填充q1，保证q1还是k个数，q2堆顶弹出。

 1 #include<queue>
 2 #include<cstdio>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 int n, k, p;
 7 int pre;
 8 priority_queue<int> q1, q2;
 9 int main()
10 {
11     scanf("%d%d%d", &n, &k, &p);
12     for(int i = 1; i <= n; i++)
13     {
14         int opt;
15         scanf("%d", &opt);
16         if(opt == 1)
17         {
18             int x;
19             scanf("%d", &x);
20             if(p == 1) x ^= pre;
21             if(q1.size() < k)
22                 q1.push(-x);
23             else
24             {
25                 q1.push(-x);
26                 q2.push(-q1.top());
27                 q1.pop();
28             }
29         }
30         else
31         {
32             pre = -q1.top();
33             printf("%d\n", pre);
34             q1.pop();
35             if(!q2.empty())
36                 q1.push(-q2.top()), q2.pop();
37         }
38     }
39     return 0;
40 }

View Code