資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究C++ 在序列上執行特定操作
假設我們給定一個空序列和 n 個查詢，我們需要處理這些查詢。這些查詢以陣列查詢形式給出，並採用 {查詢，資料} 的格式。查詢可以是以下三種類型之一：
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
更新於：02-Mar-2022
338 瀏覽量
廣告