मान लीजिए एक खाली अनुक्रम और n क्वेरी दी गई हैं जिन्हें प्रोसेस करना है। क्वेरी 'queries' सरणी में दी गई हैं और उनका प्रारूप {query, data} है। क्वेरी तीन प्रकार की हो सकती हैं:
- query = 1: दिए गए data को अनुक्रम के अंत में जोड़ें।
- query = 2: अनुक्रम के शुरुआत के तत्व को प्रिंट करें। उसके बाद उस तत्व को हटा दें।
- query = 3: अनुक्रम को आरोही क्रम में सॉर्ट करें।
ध्यान दें कि क्वेरी प्रकार 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 होगा।
प्रत्येक क्वेरी के बाद अनुक्रम निम्न है:
- 1: {5}
- 2: {5, 4}
- 3: {5, 4, 3}
- 4: {5, 4, 3, 2}
- 5: {5, 4, 3, 2, 1}
- 6: {4, 3, 2, 1}, प्रिंट 5।
- 7: {1, 2, 3, 4}
- 8: {2, 3, 4}, प्रिंट 1।
- 9: {2, 3, 4}
चरण
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
प्राथमिकता कतार priq परिभाषित करें
एक कतार q परिभाषित करें
i := 0 से n-1 तक:
operation := queries[i] का पहला मान
यदि operation == 1, तो:
x := queries[i] का दूसरा मान
x को q में डालें
अन्यथा यदि operation == 2, तो:
यदि priq खाली है, तो:
q के पहले तत्व को प्रिंट करें
q से पहला तत्व हटाएँ
अन्यथा:
-(priq के शीर्ष तत्व) को प्रिंट करें
priq से शीर्ष तत्व हटाएँ
अन्यथा यदि operation == 3, तो:
जब तक q खाली न हो:
(-q का पहला तत्व) को priq में डालें और सॉर्ट करें
q से तत्व हटाएँ
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#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 operation = queries[i].first; if(operation == 1) { int x; x = queries[i].second; q.push(x); } else if(operation == 2) { if(priq.empty()) { cout << q.front() << endl; q.pop(); } else { cout << -priq.top() << endl; priq.pop(); } } else if(operation == 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; }
इनपुट
9, {{1, 5}, {1, 4}, {1, 3}, {1, 2}, {1, 1}, {2, 0}, {3, 0}, {2, 0}, {3, 0}}
आउटपुट
5 1
