[数据结构与算法]链表-移动小球

题面部分

题目描述

你有一些小球，从左到右依次编号为1,2,3,4,5,....,n。你可以执行两种指令，其中A X Y表示将编号为X的小球移到编号为Y的小球左边，B X Y表示把小球X移到小球Y的右边，指令保证合法，即X不等于Y。例如当n等于6时，小球的初始顺序为1 2 3 4 5 6，执行A 1 4后的顺序为2 3 1 4 5 6，继续执行B 3 5之后的顺序为：2 1 4 5 3 6

输入

输入第一行包括两个正整数，分别是小球个数n(n<500000)和指令条数m(m<100000)，然后是m行，每行一条指令。

输出

输出执行完指令后，从左到右输出最后的序列。

样例输入?

6 2
A 1 4
B 3 5

样例输出?

2 1 4 5 3 6

思路与解答

解法一

?首先考虑朴素的做法，考虑用数组记录每个编号的小球所处的位置，移动小球时就先要在位置表中找到a和b小球所处的位置然后分情况考虑：

(在下面的说明中使用pos(x)代表编号为x的小球所处的位置（下标从1开始）)

• 如果读入“a”，即小球a要移动到小球b的左侧，那么就将从pos(a)到pos(b-1)的对应位置的小球的pos减一，从pos(b)到结尾的对应位置的小球的pos加一
• 如果读入“b”，即小球a要移动到小球b的右侧，那么就将从pos(a)到pos(b)的对应位置的小球的pos减一，从pos(b+1)到结尾的对应位置的小球的pos加一

在这个做法中，我们每进行一步操作就要在位置表中找到对应的两个小球的位置(查找的过程可以用哈希表创建小球编号和位置的索引所以复杂度是O(1)的)，然后改变对应位置的编号的小球的下标。

这种做法的时间复杂度是O(m*n)的，显然会超时。

解法二

下面考虑时间复杂度为O(m+n)的做法：

考虑存储每个小球对应的左边小球的编号和右边小球的编号，从而我们可以想到使用双向链表来实现，为简化代码，采用数组来模拟链表。

链表的前 (pre)指针为 left? ,后 (next)指针为 right，于是乎我们每读入一个操作就可以在O(1)的时间内更改两个对应小球的左右小球和它们自己的左右位置关系，然后输出。

1. 设计链表，我们定义成一个结构体数组，注意开辟足够的空间因为小球的数量达到了5e5级别所以要在全局区开辟空间，其下标对应小球的编号.
2. 初始化链表，将每个小球的左指针和右指针初始化.
3. 读入命令，首先将第一个小球从这个假想的队列中拿去，所以相当于删除操作，我们改变其左右小球的位置关系，然后再根据操作类型插入。无论是在小球b左边插入还是在右边插入，我们都要更新小球a的左右位置，然后更新小球b原来的左右两个小球的位置.
4. 找到头一个小球的位置,根据初始化时的语句如果左指针为0该小球为头一个小球
5. 遍历链表输出

时间复杂度:初始化链表和读取链表和找头指针的时间是O(n），读入操作命令进行移动的时间是O(m),总时间复杂度O(m+n)?

代码实现?

?

// Problem: A: 链表-移动小球
// Contest: BUCTOJ
// URL: https://buctoj.com/problem.php?cid=2749&pid=0
// Memory Limit: 128 MB
// Time Limit: 1000 ms

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
const int N = 5e5 + 10;
const int MOD = 1e9 + 7;
#define endl '\n'
#define PY puts("Yes")
#define PN puts("No")
struct Ball
{
    int left, right;
} ball[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) //初始化
    {
        ball[i].left = i - 1;
        ball[i].right = i + 1;
    }
    while (m--)
    {
        char od;
        int a, b;
        cin >> od >> a >> b;
        //将小球a移除
        ball[ball[a].left].right = ball[a].right;
        ball[ball[a].right].left = ball[a].left;
        if (od == 'A')
        {
        	//先插入小球a
            ball[a].left = ball[b].left;
            ball[a].right = b;
            //更新b的左右
            ball[ball[b].left].right = a;
            ball[b].left = a;
        }
        else if (od == 'B')
        {
            ball[a].left = b;
            ball[a].right = ball[b].right;
            ball[ball[b].right].left = a;
            ball[b].right = a;
        }
    }
    //寻找头一个小球
    int start = 1;
    while (start < n && ball[start].left)
        start++;
    int x = start;
    //输出答案
    while (x != n + 1)
    {
        cout << x << " ";
        x = ball[x].right;
    }
    return 0;
}