首页 > 代码库 > HDU 4286 Data Handler (双端队列)

HDU 4286 Data Handler (双端队列)

2024-07-22 08:06:26   225人阅读

Data Handler

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2455    Accepted Submission(s): 616


Problem Description
　　You are in charge of data in a company, so you are called "Data Handler". Different from the data in computer, the data you have are really in huge volume, and each data contains only one integer. All the data are placed in a line from left to right. There are two "hand" to handle the data, call hand "L" and hand "R". Every hand is between two adjacent data or at the end of the data line.
　　In one day, the company gives you many commands to handle these data, so you should finish them one by one. At the beginning, there are N data, and hand "L" and "R" are in some positions. Each command is one the following formats:
　　(1)MoveLeft L/R: it means that you should move the hand "L"/"R" left one data unit;


　　(2)MoveRight L/R: it means that you should move the hand "L"/"R" right one data unit;



　　(3)Insert L X: it means that you should insert the data that contains X at the right of the hand "L";



　　(4)Insert R X: it means that you should insert the data that contains X at the left of the hand "R";



　　(5)Delete L: it means that you should delete the one data at the right of the hand "L";



　　(6)Delete R: it means that you should delete the one data at the left of the hand "R";



　　(7)Reverse: it means that you should reverse all the data between hand "L" and hand "R".


　　After finish all the commands, you should record all the data from left to right. So please do it.
 

Input
　　The first line contains an integer T(1<=T<=10), the number of test cases.
　　Then T test cases follow. For each test case, the first line contains an integer N(1<=N<=500000), the number of data at the beginning. The second line contains N integers, means the integer in each data, from left to right. The third line contains two integers L and R (1<=L<=R<=N), the positions of hand "L" and hand "R". It means that hand "L" is at the left of the L-th data and hand "R" is at the right of the R-th data. The fourth line contains one integer M(1<=M<=500000), the number of commands. Then M lines follow, each line contains a command in the above format. All the integers in the data will in range [-10000,10000].
　　It is guaranteed that there are always some data between hand "L" and "R", and if the hand is at the left/right end of the data line, it will not receive the command MoveLeft/MoveRight.
　　Because of large input, please use scanf instead of cin.
 

Output
　　For each test case, output the integers in the data from left to right in one line, separated in a single space.
　　Because of large output, please use printf instead of cout.
　　
 

Sample Input
2
5
1 2 3 4 5
1 5
5
MoveLeft R
Insert R 6
Reverse
Delete R
Insert L 7
5
6536 5207 2609 6604 -4046
1 3
5
Delete L
Insert R -9221
Reverse
Delete L
MoveRight L
 

Sample Output
7 6 4 3 2 5
2609 5207 6604 -4046
 
题意：给你一个链表 和左右两个指针，六种操作，最后按顺序输出剩下的数字
思路：与SGU271相似，用双端队列维护左右指针之间的数字，用两个双端队列维护左指针左边的数和右指针右边的数。用一个变量标记是否经过翻转：可以理解成翻转以后双端队列的两个头发生了转变。特别需要注意的是 MoveRight 和 MoveLeft。插入的头是有所变化的！
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
const int maxn = 500000+10;
#define REP(_,a,b) for(int _ = (a); _ <= (b); _++)
int n,m,dir;
deque<int> dqi,lft,rgt;
int Lp,Rp;
int num[maxn];
void init() {
    dqi.clear();
    lft.clear();
    rgt.clear();
    dir = 1;
}
void input() {
    scanf("%d",&n);
    REP(i,1,n) scanf("%d",&num[i]);
    scanf("%d%d",&Lp,&Rp);
    REP(i,1,Lp-1 ) lft.push_back(num[i]);
    REP(i,Lp,Rp) dqi.push_back(num[i]);
    REP(i,Rp+1,n ) rgt.push_back(num[i]);
    scanf("%d",&m);
}
void Reverse() {
    dir = 1-dir;
}
void Insert() {
    char op[20];
    int x;
    scanf("%s%d",op,&x);
    if( (op[0]=='R' && dir) || (op[0] =='L' && !dir) ) {
        dqi.push_back(x);
    } else {
        dqi.push_front(x);
    }
}
void Delete() {
    char op[20];
    scanf("%s",op);
    if( (op[0]=='R' && dir) || (op[0] =='L' && !dir) ) {
        dqi.pop_back();
    } else {
        dqi.pop_front();
    }
}
void MoveLeft() {
    char op[20];
    scanf("%s",op);
     if( op[0]=='L' && dir ){
        int x = lft.back();
        lft.pop_back();
        dqi.push_front(x);
    }else if( op[0]=='R' && !dir ){
        int x = dqi.front();
        dqi.pop_front();
        rgt.push_front(x);
    }
    else if(op[0] == 'R' && dir){
        int x = dqi.back();
        dqi.pop_back();
        rgt.push_front(x);
    } else {
        int x = lft.back();
        lft.pop_back();
        dqi.push_back(x);
    }
}
void MoveRight() {
    char op[20];
    scanf("%s",op);
    if( (op[0]=='L' && dir)) {
        int x = dqi.front();
        dqi.pop_front();
        lft.push_back(x);
    }
    else if(op[0]=='R' && dir) {
        int x = rgt.front();
        rgt.pop_front();
        dqi.push_back(x);

    }
    else if(op[0]=='L' && !dir){
        int x = dqi.back();
        dqi.pop_back();
        lft.push_back(x);
    }else{
        int x = rgt.front();
        rgt.pop_front();
        dqi.push_front(x);
    }
}
void output() {
    bool flag = false;
    for(deque<int>::iterator it = lft.begin(); it != lft.end(); it++) {
        if(!flag) {
            printf("%d",*it);
            flag = true;
        } else {
            printf(" %d",*it);
        }
    }

    if(!dir) reverse(dqi.begin(),dqi.end());
    for(deque<int>::iterator it = dqi.begin(); it != dqi.end(); it++) {
        if(!flag) {
            printf("%d",*it);
            flag = true;
        } else {
            printf(" %d",*it);
        }
    }
    for(deque<int>::iterator it = rgt.begin(); it != rgt.end(); it++) {
        if(!flag) {
            printf("%d",*it);
            flag = true;
        } else {
            printf(" %d",*it);
        }
    }
    puts("");
}
void solve() {
    char cmd[20];
    while(m--) {
        scanf("%s",cmd);
        if(cmd[0]=='R') Reverse();
        else if(cmd[0]=='I') Insert();
        else if(cmd[0] == 'D') Delete();
        else if(cmd[0]=='M' && cmd[4]=='R') MoveRight();
        else MoveLeft();
    }
    output();
}
int main(){

    int ncase;
    cin >> ncase;
    while(ncase--) {
        init();
        input();
        solve();
    }
    return 0;
}



HDU 4286 Data Handler (双端队列)


联系
我们