P1801:黑匣子题解

主要思路

我们可以考虑一个神仙结构:对顶堆。创建大根堆\(qmax\)和小根堆\(qmin\)。我们先用数组来储存这些数据。然后针对于某一次询问,我们要找整个序列前\(u(i)\)个数中第\(i\)小的的数字。每一次询问时,我们都把前\(u(i)\)个数放入大根堆中,如果大根堆中的元素数量等于\(i\)时,我们就把大根堆中最大的数(堆顶)放入小根堆中。最后,大根堆的元素个数为\(i-1\),然后我们要找的第\(i\)小的一定在小根堆的堆顶。

为什么?因为我们每次都是把大根堆堆顶放入小根堆中的,说明小根堆中的所有数都大于大根堆中的所有数。然后大根堆维护了\(i-1\)个数,然后第\(i\)大的数自然就在小根堆的堆顶。

代码

// P1801.cpp
#include <iostream>
#include <cstdio>
#include <queue>
#define ll long long
using namespace std;
const int maxn = 210000;
ll M, N, arr[maxn], num, idx = 0, r = 1;
priority_queue<ll> qmax;
priority_queue< ll, vector<ll>, greater<ll> > qmin;
int main()
{
    scanf("%lld%lld", &M, &N);
    for (int i = 1; i <= M; i++)
        scanf("%lld", &arr[i]);
    for (int i = 1; i <= N; i++)
    {
        scanf("%lld", &num), idx++;
        for (int prev = r; prev <= num; prev++)
        {
            qmax.push(arr[prev]);
            if (i == qmax.size())
                qmin.push(qmax.top()), qmax.pop();
        }
        r = num + 1;
        printf("%d\n", qmin.top()), qmax.push(qmin.top()), qmin.pop();
    }
    return 0;
}

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注