唉,太菜了。两个容器,一个容量为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 }
原文:https://www.cnblogs.com/Jony-English/p/12926368.html