T69293 maintenance queue
topic description
Alice gave Bob has arranged a lot of work. He is so busy that he decides to process these tasks in a “first in first out (FIFO)” order. But in the process, Bob realizes that this order may not be optimal, so he will selectively postpone certain tasks.
In abstract, you need to maintain a queue to support three operations:
Operation 1: 1v, add a value of v’s task. span>
Operation 2: 2, if the current queue is empty, output –< span class="katex">1; otherwise, output the value of the head of the team and pop the head of the team. span>
Operation 3: 3, if the current queue is empty, no operation will be performed; otherwise, the value in the queue will be The smallest task is moved to the end of the team to ensure that there is no task of equal value.
input and output format
input format:
An integer in the first line n, which means the number of operations.
Next n Line, one or two integers per line, the format is as above.
Output format:
< p>
For each operation 2 , output the answer.
Input and output sample
Input sample#1:
5
1 1
1 2
2
2
2
Output example #1:
1
2
-1
Input sample#2: < br>
6
1 1
1 2
3
2
2
2
Output example #2:
2
1
-1
[Problem Solution]:
After listening to the explanation, I found this idea very interesting.
Actually, the general queues of Push and Pop can be maintained, but you need to use your brains for Mov operations.
In fact, Mov does not necessarily need to move. What is needed is the mark, the minimum mark, and then use Set to find the position of the minimum,
then Push the historical number in.
The Val[No] obtained can be used as an array to save the value of the history number.
Push() Entering the queue is not only a queue, but also a Set.
Pop() When popping up, notice that some of the ones marked with Mov may appear at the head of the line. Remember to pop it up.
The Mov() operation involves two problems.
The first one: Use the head element of Set to be the minimum value, and at the same time Set stores the type of pair,
The first keyword is: weight, val, and the second keyword is: history number, No
Set directly finds the corresponding history number for marking.
At the same time, delete it in Set, and then push a val value again for the queue.
Attach code:
1 #include
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()) < span style="color: #0000ff;">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()) < span style="color: #0000ff;">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 ",pop());
41 }else{
42 mov();
43 }
44 }
45 return 0;
46 }
Maintenance queue
Input example#1:
5
1 1
1 2
2
2
2
Output example #1:
1
2
-1
Input example #1:
5
1 1
1 2
2
2
2
Output sample #1:
1
2
-1
Input example#2:
6
1 1
1 2
3
2
2
2
Output example #2:
2
1
-1
[Problem Solution]:
After listening to the explanation, I found this idea very interesting.
Actually, the general queues of Push and Pop can be maintained, but you need to use your brains for Mov operations.
In fact, Mov does not necessarily need to move. What is needed is the mark, the minimum mark, and then use Set to find the position of the minimum,
then Push the historical number in.
The Val[No] obtained can be used as an array to save the value of the history number.
Push() Entering the queue is not only a queue, but also a Set.
Pop() When popping up, notice that some of the ones marked with Mov may appear at the head of the line. Remember to pop it up.
The Mov() operation involves two problems.
The first one: Use the head element of Set to be the minimum value, and at the same time Set stores the type of pair,
The first keyword is: weight, val, and the second keyword is: history number, No
Set directly finds the corresponding history number for marking.
At the same time, delete it in Set, and then push a val value again for the queue.
Attach code:
1 #include
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()) < span style="color: #0000ff;">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()) < span style="color: #0000ff;">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 ",pop());
41 }else{
42 mov();
43 }
44 }
45 return 0;
46 }
Maintenance queue
Input example #2:
6
1 1
1 2
3
2
2
2
Output sample #2:
2
1
-1
[Problem Solution]:
After listening to the explanation, I found this idea very interesting.
Actually, the general queues of Push and Pop can be maintained, but you need to use your brains for Mov operations.
In fact, Mov does not necessarily need to move. What is needed is the mark, the minimum mark, and then use Set to find the position of the minimum,
then Push the historical number in.
The Val[No] obtained can be used as an array to save the value of the history number.
Push() Entering the queue is not only a queue, but also a Set.
Pop() When popping up, notice that some of the ones marked with Mov may appear at the head of the line. Remember to pop it up.
The Mov() operation involves two problems.
The first one: Use the head element of Set to be the minimum value, and at the same time Set stores the type of pair,
The first keyword is: weight, val, and the second keyword is: history number, No
Set directly finds the corresponding history number for marking.
At the same time, delete it in Set, and then push a val value again for the queue.
Attach code:
1 #include
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()) < span style="color: #0000ff;">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()) < span style="color: #0000ff;">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 ",pop());
41 }else{
42 mov();
43 }
44 }
45 return 0;
46 }
Maintenance queue
1 #include
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 ",pop());
41 }else{
42 mov();
43 }
44 }
45 return 0;
46 }
维护队列
1 #include
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 ",pop());
41 }else{
42 mov();
43 }
44 }
45 return 0;
46 }