ধরুন, আমাদের একটি খালি ক্রম এবং n প্রশ্ন দেওয়া হয়েছে যা আমাদের প্রক্রিয়া করতে হবে। প্রশ্নগুলি অ্যারে কোয়েরিতে দেওয়া হয় এবং সেগুলি বিন্যাসে থাকে {query, data}৷ প্রশ্নগুলি নিম্নলিখিত তিনটি প্রকারের হতে পারে-
-
query =1:অনুক্রমের শেষে সরবরাহকৃত ডেটা যোগ করুন।
-
query =2:অনুক্রমের শুরুতে উপাদানটি প্রিন্ট করুন। এর পরে উপাদানটি মুছুন।
-
query =3:ক্রম ক্রমবর্ধমান ক্রমে সাজান।
মনে রাখবেন, কোয়েরি প্রকার 2 এবং 3-এ সর্বদা ডেটা =0 থাকে।
সুতরাং, যদি ইনপুটটি n =9 এর মত হয়, প্রশ্ন ={{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}
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
priority_queue<int> priq Define one queue q for initialize i := 0, when i < n, update (increase i by 1), do: operation := first value of queries[i] if operation is same as 1, then: x := second value of queries[i] insert x into q otherwise when operation is same as 2, then: if priq is empty, then: print first element of q delete first element from q else: print -(top element of priq) delete top element from priq otherwise when operation is same as 3, then: while (not q is empty), do: insert (-first element of q) into priq and sort delete element from 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