[伯俊]二重優先順位Q#7662

13975 ワード
7662 白駿 テキストリンク
説明:
2つの優先キュー(minheap、maxheap)を一緒に配置し、各同期を調整して問題を解決します.
今度の問題からjsで解くと同じ論理でもメモリオーバーフローが頻繁に発生するのでC++だけで解くべきだと思います.
C++プール
#include<bits/stdc++.h>
using namespace std;

const int MAX = 1000003;
bool visited[MAX];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N; cin >> N;
    while(N--) {
        int M; cin >> M;
        priority_queue<pair<int, int>> maxPQ;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minPQ;
        for (int i=0; i<M; i++) {
            char command; int num;
            cin >> command >> num;
            if (command == 'I') {
                minPQ.push({num, i});
                maxPQ.push({num, i});
                visited[i] = true;
            } else if (command == 'D') {
                if (num == 1) {
                    while(!maxPQ.empty() && !visited[maxPQ.top().second]) maxPQ.pop();
                    if (maxPQ.empty()) continue;
                    visited[maxPQ.top().second] = false;
                    maxPQ.pop();
                }
                else if (num == -1) {
                    while(!minPQ.empty() && !visited[minPQ.top().second]) minPQ.pop();
                    if (minPQ.empty()) continue;
                    visited[minPQ.top().second] = false;
                    minPQ.pop();
                }
            }
        }
        while(!maxPQ.empty() && !visited[maxPQ.top().second]) maxPQ.pop();
        while(!minPQ.empty() && !visited[minPQ.top().second]) minPQ.pop();

        if (minPQ.empty() || maxPQ.empty()) cout << "EMPTY" << '\n';
        else cout << maxPQ.top().first << ' ' << minPQ.top().first << '\n';
    }
    return 0;
}
100のプロジェクト71 -電子メール設定ページRedux
Elixirタスクモジュールのパワー-タスクに.主任