使用C++对序列执行特定操作

假设我们有一个空序列和n个需要处理的查询。查询以数组queries的格式给出，格式为{query，data}。查询可以有以下三种类型：

• query = 1：将提供的数据添加到序列的末尾。

• query = 2：打印序列开头的元素。然后删除该元素。

• query = 3：按升序对序列进行排序。

  立即学习“C++免费学习笔记（深入）”；

注意，查询类型2和3的data始终为0。

Magic AI Avatars

神奇的AI头像，获得200多个由AI制作的自定义头像。

下载

因此，如果输入是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}

要解决这个问题，我们将按照以下步骤进行：

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

Example

让我们来看下面的实现，以便更好地理解 −

#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