对顶堆

对顶堆就是通过一个小根堆和一个大根堆来动态维护一个序列上第k大或者第K小的数

序列左侧用小根堆维护，右侧用大根堆维护。

如果题目要求不断动态输出第K大的数，那么小根堆的堆元素就是第K大的元素，大根堆的堆顶元素就是第K+1大的元素。

RMID2 - Running Median Again

https://www.luogu.com.cn/problem/SP15376

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const int inf = 2147483647;
const ll INF = 1e18;
void solve(){
    int x;
    priority_queue<int,vector<int>,greater<int>>a;
    priority_queue<int,vector<int>,less<int>>b;
    while(cin>>x&&x)
    {
        if(x==-1)
        {
            cout<<b.top()<<'\n';
            b.pop();
        }
        else 
        {
            if(b.size()&&x<=b.top())b.push(x);//感觉就是随便选一个塞进去,然后再调整
            else  a.push(x);
        }
        if(b.size()>(a.size()+b.size()+1)/2)
        {
            a.push(b.top());
            b.pop();
        }
        else if(b.size()<(a.size()+b.size()+1)/2)
        {
            b.push(a.top());
            a.pop();
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;cin>>tt;
    while(tt--){
        solve();
    }


    return 0;    
}

P1801 黑匣子

https://www.luogu.com.cn/problem/P1801

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
using u32 = unsigned;
#define i128 __int128;
using ll = long long;
//#define int ll
using u64 = unsigned long long;
const int inf = 2147483647;
const ll INF = 1e18;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<int>k(n+1),v(m+1);
    priority_queue<int,vector<int>,greater<int>>a;
    priority_queue<int,vector<int>,less<int>>b;
    for(int i=1;i<=n;i++)cin>>k[i];
    for(int i=1;i<=m;i++)cin>>v[i];
    sort(v.begin()+1,v.end());
    int dix=1;
    int geshu=0;
    for(int i=1;i<=n;i++)
    {
        int x=k[i];
         // 感觉这一种思路是最方便的
        b.push(x);// 这三行代码直接把x添加到b之中，让b先进行排序，然后再把堆顶元素弹到a中
        a.push(b.top());
        b.pop();
        while(dix<=m&&v[dix]==i)
        {
            b.push(a.top());
            a.pop();
            cout<<b.top()<<"\n";
            dix++;
        }
    }

    return 0;    
}