C++对顶堆(求第k大、k小数)+P1801题解

这里借鉴了一些别人题解的思路,仅供自己收藏使用。

题目大意:动态修改数组,求第k小的数。

from:7KByte P1801题解

对此,POISONN大佬发表了他的意见:楼主写法应该是让大根堆里有k-1个元素,然后小根堆的堆顶才是第k小数吧?

(大概是因为单纯地在大根堆插入元素无法保证对顶堆中,大根堆元素恒小于小根堆的性质,所以需要让大根堆顶元素移动至小根堆吧?)

私认为他说得有道理。

Code: 以LuoguP1801 黑匣子为例

/*
模拟样例:
a:[3 1 -4 2 8 -1000 2]
u:[1 2 6 6]
A:[] (大根堆)
B:[] (小根堆)
i=1: pos=1,u=1  for[1]:j=1 A:[3] B:[3] A:[]
                cout<<3
                A:[3] B:[]
i=2: pos=2,u=2  for[1]:j=2 A:[3 1] B:[3] A:[1]
                cout<<3
                A:[3 1] B:[]
i=3: pos=3,u=6  for[1]:j=3 A:[3 1 -4] B:[3] A:[1 -4]
                for[2]:j=4 A:[2 1 -4] B:[2 3] A:[1 -4]
                for[3]:j=5 A:[8 1 -4] B:[2 3 8] A:[1 -4] 
                for[4]:j=6 A:[1 -4 -1000] B:[1 2 3 8] A:[-4 -1000]
                cout<<1
                A:[1 -4 -1000] B:[2 3 8]
i=4: pos=7,u=6  循环不执行
                cout<<2
                A:[2 1 -4 -1000] B:[3 8]
*/

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 7;

int a[200005];

int main()
{   
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    priority_queue <int> A; // 大根堆
    priority_queue <int, vector<int>, greater<int>> B; // 小根堆
    int n, m; cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> a[i];

    int pos = 1;
    for(int u, i = 1; i <= m; i ++){ // 这个i就是GET查询中的i
        cin >> u;
        for(int j = pos; j <= u; j ++){ // 让第u个元素放入(可以这样做是因为题目说“保证u序列单调不降”)
            A.push(a[j]);
            if(A.size() == i) B.push(A.top()), A.pop();
        }
        pos = u + 1; // 表明当前a数组的下一次add操作应放入a[u+1]
        cout << B.top() << '\n';
        A.push(B.top());
        B.pop();
    }

    return 0;
}

上一篇:IAR全面支持芯驰科技E3系列车规MCU产品E3119/E3118


下一篇:mysql select count返回null