洛谷 P1801 黑匣子_NOI导刊2010提高(06)

异常清晰,自己花了好长时间想出来的,继续加油!

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
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
struct BlackBox {
private:
    priority_queue<ll,vector<ll>,greater<ll> > minHeap;
    priority_queue<ll> maxHeap;
public:
    void add(ll num) {
        if (maxHeap.empty())minHeap.push(num);
        else if (num < maxHeap.top()) {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
            maxHeap.push(num);
        }
        else minHeap.push(num);
    }
    ll get() {
        ll re = minHeap.top();
        maxHeap.push(minHeap.top());
        minHeap.pop();
        return re;
    }
}BB;
int m, n;
ll arr1[200005], arr2[200005];
ll arr2Ptr = 1;
int main() {
    ios::sync_with_stdio(false);
    cin >> m >> n;
    for (int i = 1; i <= m; i++) cin >> arr1[i];
    for (int i = 1; i <= n; i++)cin >> arr2[i];
    for (int i = 1; i <= m; i++) {
        BB.add(arr1[i]);
        while (arr2[arr2Ptr] == i) {
            cout << BB.get() << endl;
            arr2Ptr++;
        }
    }
}

发表评论

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