
假设我们有一个空序列和n个需要处理的查询。查询以数组queries的格式给出,格式为{query,data}。查询可以有以下三种类型:
query = 1:将提供的数据添加到序列的末尾。
query = 2:打印序列开头的元素。然后删除该元素。
query = 3:按升序对序列进行排序。
立即学习“C++免费学习笔记(深入)”;
注意,查询类型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。
每个查询后的序列如下所示:
要解决这个问题,我们将按照以下步骤进行:
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
以上就是使用C++对序列执行特定操作的详细内容,更多请关注php中文网其它相关文章!
c++怎么学习?c++怎么入门?c++在哪学?c++怎么学才快?不用担心,这里为大家提供了c++速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号