概述

这道题实际上之前做过一遍,但是神奇地哪里都找不到了。想法是大约半年前的想法,重新实现了一下。

没有什么好说的,静态双向链表,实现左侧插入和右侧插入。速度要比STL list快很多。

 

题目描述

你有一些小球,从左到右依次编号为1,2,3,…,n,如下图所示。
你可以执行两种指令。A X Y 把小球X移动到Y左边;B X Y 把小球X移动到Y右边。指令保证合法(X与Y不同)。

输入描述

输入: 第一行是2个正整数,第一个正整数是小球个数n,第二个正整数是指令条数m;随后输入m条指令。

输出描述

从左到右输出最后的序列中各小球序号。序号之间使用空格隔开。行末没有空格。

样例输入

6 2

A 1 4

B 3 5

样例输出

2 1 4 5 3 6

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 2000;

int pre[N], nxt[N];

int main() {
    char t;
    int x, y, l, r;
    for(int n, m; ~scanf("%d%d", &n, &m);) {
        for(int i = 0; i <= n; i++) {
            pre[i + 1] = i;
            nxt[i] = i + 1;
        }
        pre[0] = -1;
        nxt[n + 1] = -1;
        while(m--) {
            while(!isalpha(t = getchar()));
            scanf("%d%d", &x, &y);
            l = pre[x], r = nxt[x];
            nxt[l] = r, pre[r] = l;
            if(t == 'A') {
                l = pre[y], r = y;
            } else {
                l = y, r = nxt[y];
            }
            nxt[l] = x, nxt[x] = r;
            pre[x] = l, pre[r] = x;
        }
        printf("%d", nxt[0]);
        for(int j = nxt[nxt[0]]; ~nxt[j]; j = nxt[j]) {
            printf(" %d", j);
        }
        putchar('\n');
    }
    return 0;
}

 

CC BY-NC-SA 4.0 本作品使用基于以下许可授权:Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注