加入收藏 | 设为首页 | 会员中心 | 我要投稿 辽源站长网 (https://www.0437zz.com/)- 云专线、云连接、智能数据、边缘计算、数据安全!
当前位置: 首页 > 服务器 > 安全 > 正文

【数据结构】维护队列

发布时间:2021-04-03 07:16:17 所属栏目:安全 来源:网络整理
导读:T69293 维护队列 题目描述 Alice 给 Bob 布置了很多工作,他忙的不可开交,决定按照“先进先出(FIFO)”的顺序依次处理这些工作。但是处理过程中,Bob 意识到这种顺序可能不是最优的,因此他会选择性的把某些工作延后。 抽象来说,你需要维护一个队列,支持三

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值。

附上代码:

【数据结构】维护队列

【数据结构】维护队列

 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("%dn",pop());
41         }else{
42             mov();
43         }
44     }
45     return 0;
46 }
维护队列

(编辑:辽源站长网)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读