A27721. 整理书本(book)
填空题
中等
知识点
题目描述
整理书本(book)
题目描述：又一个学期结束了，又积累了好多本书，你决定好好整理一下，整理时共有三种操作，规则如下：
1、p 表示把编号为 p 的书放到最前面
2、p 表示把编号为 p 的书放到最后面
3、p q 表示把编号为 p 的书放到编号为 q 的书的后面
1、2、3 分别代表整理操作的种类，p、q 表示书的编号，他们之间由空格分隔；已知在整理之前，所有书从 1 开始依次编号排放。
输入
共 m+1 行。第一行有两个由空格分隔的正整数 n 和 m，分别表示 n 本书和 m 次整理操作，接下来 m 行，每行有 2 个或 3 个由空格分隔的正整数，
对应上述三种整理操作。
输出
共 1 行，经过整理后的书本顺序，书本间用空格隔开。
样例输入
10 4
1 3
2 4
3 3 6
3 1 5
样例输出
2 5 1 6 3 7 8 9 10 4
数据范围
1≤n,m≤100000
参考答案
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct node {
int pre,next,data;
} a[N];
int n,m;
void init() {
for(int i=1; i<=n; i++) {
a[i].pre = i-1;
a[i].data = i;
a[i].next = i+1;
}
}
int main() {
scanf("%d%d",&n,&m);
init();
int head = 1,end = n;
while(m--) {
int op,p;
scanf("%d%d",&op,&p);
int pre = a[p].pre;
int nxt = a[p].next;
if(op==1) { //放到最前面
if(pre == 0) continue;
if(nxt == n+1) end = pre; //换尾
else a[nxt].pre = pre;
a[head].pre = p;
a[pre].next = nxt;
a[p].next = head;
a[p].pre = 0;
head = p; //换头
} else if(op==2){
if(nxt == n+1) continue;
if(pre == 0) head = nxt; //换头
else a[pre].next = nxt;
a[nxt].pre = pre;
a[end].next = p;
a[p].next = n+1;
a[p].pre = end;
end = p;//换尾
} else {
int q;
scanf("%d",&q);
if(a[q].next == p|| p==q) continue;
if(pre == 0) { //换头
head = nxt;
a[head].pre = 0;
}
if(nxt == n+1) { //换尾
end = pre;
a[end].next = n+1;
}
if(q == end) end = p;
a[nxt].pre = pre;
a[pre].next = nxt;
a[p].next = a[q].next;
a[p].pre = q;
a[a[q].next].pre = p;
a[q].next = p;
}
}
for(int i=1; i<=n; i++) {
cout<<a[head].data<<" ";
head = a[head].next;
}
return 0;
}
上一题
下一题