【数据结构】维护队列

系统管理员 2021-12-11 12:37 219阅读 0赞

# T69293 维护队列 #

## 题目描述 ##

Alice 给 Bob 布置了很多工作，他忙的不可开交，决定按照“先进先出(FIFO)”的顺序依次处理这些工作。但是处理过程中，Bob 意识到这种顺序可能不是最优的，因此他会选择性的把某些工作延后。

抽象来说，你需要维护一个队列，支持三种操作：

操作一：1 v，在队尾加入一个价值为 v 的任务。

操作二：2，如果当前队列为空，输出 -1；否则输出队头任务的价值，并将队头弹出。

操作三：3，如果当前队列为空，则不进行任何操作；否则将队列中价值最小的任务挪到队尾，保证没有价值相等的任务。

## 输入输出格式 ##

输入格式：

第一行一个整数 n，表示操作个数。

接下来 n 行，每行一个或两个整数，格式如上。

输出格式：

对于每个操作 2，输出答案。

## 输入输出样例 ##

输入样例\#1：

5
    1 1
    1 2
    2
    2
    2

输出样例\#1：

1
    2
    -1

输入样例\#2：

6
    1 1
    1 2
    3
    2
    2
    2

输出样例\#2：

2
    1
    -1

--------------------

【题解】：
    听过讲解之后，发现这个想法非常有趣。
    其实Push，Pop一般队列都可以维护，但是对于Mov操作就需要大家开动一下脑筋了。
    其实Mov不一定需要移动。需要的是标记，最小值标记，然后用Set来查找最小值的位置，
    然后Push进去的历史编号。
    得到的Val[No] 用数组来保存历史编号的值即可。
    Push( ) 进入队列不仅仅是队列，还有Set。
    Pop( ) 弹出时注意，有些用Mov标记的可能出现在队头，记得要把它弹出。
    Mov( )操作涉及到两个问题。
    第一个：用Set的头元素即为最小值的，同时Set存的是pair类型，
    第一关键字是：权值，val，第二关键字为：历史编号 ，No
    Set直接找到对应的历史编号进行标记。
    同时在Set删除，然后对于队列来说，重新Push进去一个val值。
    
    附上代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 const int N = 3e5+100;
     4 queue <int> Q ;
     5 set< pair<int,int> > S;
     6 int cur ,val[N] , top ;
     7 bool deleted[N];
     8 void push( int v ){
     9     cur ++ ;
    10     val[cur] = v;
    11     Q.push(cur);
    12     S.insert( make_pair(v,cur) );
    13 }
    14 int pop(){
    15     if( S.empty() ) return -1;
    16     while( deleted[Q.front()] ){
    17         Q.pop();
    18     }
    19     int ret = Q.front();
    20     Q.pop();
    21     S.erase( make_pair(val[ret],ret) );
    22     return val[ret];
    23 }
    24 void mov(){
    25     if( S.empty() ) return ;
    26     deleted[S.begin()->second] = true ;
    27     push(val[S.begin()->second]);
    28     S.erase( S.begin() );
    29 }
    30 int main()
    31 {
    32     int n,opt,v;
    33     scanf("%d",&n);
    34     while(n--){
    35         scanf("%d",&opt);
    36         if( opt == 1 ){
    37             scanf("%d",&v);
    38             push(v);
    39         }else if( opt == 2 ){
    40             printf("%d\n",pop());
    41         }else{
    42             mov();
    43         }
    44     }
    45     return 0;
    46 }

维护队列

转载于:https://www.cnblogs.com/Osea/p/10995068.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211211/3bb57650f98449c4bb68b4b2e3c87f59.png