uva 501 - Black Box(優先隊列)

uva 501 - Black Box(優先隊列)

題目鏈接：uva 501 - Black Box

題目大意：有一個集合，給定元素進入集合的順序，現在有Q次查詢，給定每次查詢在第幾個元素進入集合後，對於每i次查詢，輸出集合中第i小的數。

解題思路：用兩個優先隊列維護，隊列a優先出值大的，隊列b優先出值小的，在第i次詢問前，保證a隊列中有i-1個元素元素，並且抱枕都比b中的小，然後每次詢問輸出b隊列的首元素，並且將它放到a隊列中。

#include 
#include 
#include 
#include 

using namespace std;
const int maxn = 30005;

int N, M, arr[maxn], v[maxn];

void solve () {
    priority_queue a;
    priority_queue, greater > b;

    for (int i = 1; i <= N; i++) {
        a.push(arr[i]);
        b.push(a.top());
        a.pop();

        while (v[i]--) {
            printf("%d\n", b.top());
            a.push(b.top());
            b.pop();
        }
    }
}

int main () {
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        int x;
        memset(v, 0, sizeof(v));
        scanf("%d%d", &N, &M);

        for (int i = 1; i <= N; i++)
            scanf("%d", &arr[i]);
        for (int i = 0; i < M; i++) {
            scanf("%d", &x);
            v[x]++;
        }

        solve();

        if (cas)
            printf("\n");
    }
    return 0;
}