โปรแกรม C++ ดำเนินการกับลำดับข้อมูล (Queue + Priority Queue)

มีลำดับว่าง และ n คำสั่ง (queries) รูปแบบ {query, data} 3 ประเภท:

• query=1: เพิ่ม data ต่อท้ายลำดับ
• query=2: พิมพ์ตัวแรกของลำดับ แล้วลบออก
• query=3: เรียงลำดับจากน้อยไปมาก

หมายเหตุ: query=2,3 มี data=0 เสมอ

ตัวอย่าง: n=9, queries={{1,5},{1,4},{1,3},{1,2},{1,1},{2,0},{3,0},{2,0},{3,0}} ผลลัพธ์: 5 1

ขั้นตอนการแก้ปัญหา (Queue + Priority Queue)

1. ใช้ queue q เก็บลำดับปกติ, priority_queue priq (max-heap เก็บค่าลบ) เก็บส่วนที่เรียงแล้ว
2. query=1: push เข้า q
3. query=2: ถ้า priq ว่าง → พิมพ์ q.front() pop q; มิฉะนั้น → พิมพ์ -priq.top() pop priq
4. query=3: ย้ายทุกตัวจาก q เข้า priq (push -q.front()) แล้ว clear q

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

void solve(int n, vector<pair<int,int>> queries) {
    priority_queue<int> priq;
    queue<int> q;
    for (int i = 0; i < n; i++) {
        int op = queries[i].first;
        if (op == 1) {
            int x = queries[i].second;
            q.push(x);
        } else if (op == 2) {
            if (priq.empty()) {
                cout << q.front() << endl;
                q.pop();
            } else {
                cout << -priq.top() << endl;
                priq.pop();
            }
        } else if (op == 3) {
            while (!q.empty()) {
                priq.push(-q.front());
                q.pop();
            }
        }
    }
}

int main() {
    int n = 9;
    vector<pair<int,int>> queries = {{1,5},{1,4},{1,3},{1,2},{1,1},{2,0},{3,0},{2,0},{3,0}};
    solve(n, queries);
    return 0;
}

อินพุต / เอาต์พุต

Input: 9, {{1,5},{1,4},{1,3},{1,2},{1,1},{2,0},{3,0},{2,0},{3,0}}

Output: 5 1