【离线】左移右移【蓝桥杯】

题目

左移右移 - 蓝桥云课

---

问题描述

小蓝有一个长度为 $N$ 的数组, 初始时从左到右依次是 $1, 2, 3, \dots, N$ 。

之后小蓝对这个数组进行了 $M$ 次操作, 每次操作可能是以下 $2$ 种之一:

1. 左移 $x$, 即把 $x$ 移动到最左边。
2. 右移 $x$, 即把 $x$ 移动到最右边。

请你回答经过 $M$ 次操作之后, 数组从左到右每个数是多少?

输入格式

第一行包含 2 个整数, $N$ 和 $M$ 。

以下 $M$ 行每行一个操作, 其中 "L x" 表示左移 $x$ ，"R x" 表示右移 $x$ 。

输出格式

输出 $N$ 个数, 代表操作后的数组。

样例输入

5 3
L 3
L 2
R 1

样例输出

2 3 4 5 1

样例说明

样例中的数组变化如下:

$[1,2,3,4,5]→[3,1,2,4,5]→[2,3,1,4,5]→[2,3,4,5,1]$ 。

评测用例规模与约定

对于 $50$ 的评测用例, $1 \le N, M \le 10000$ 。

对于 $100$ 的评测用例, $1 \le, N, M, \le 200000,1 \le x \le N$ 。

运行限制

• 最大运行时间：3s
• 最大运行内存：512M

解题

方法一：离线 栈

思路

先输入所有数字及其操作并压入栈中。然后维护一个操作后的数组(ans)开始出栈离线操作，由于越靠近栈顶操作越靠后（之后的操作不会被之前的操作所影响反而可以覆盖之前的操作）于是就可以记录哪些数字已经被操作过，后出栈的已经被操作过的数字就可以直接跳过，直到栈为空。最后枚举所有数字，从前往后地把还未被操作过的数字加入数组中，输出数组即为答案。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int m = (int) in.nval;
        Deque<int[]> ops = new LinkedList<>();
        while (m-- > 0) {
            in.nextToken();
            int dir = in.sval.charAt(0) == 'L' ? 0 : 1;
            in.nextToken();
            int x = (int) in.nval;
            ops.push(new int[]{dir, x});
        }
        int[] ans = new int[n];
        int l = 0, r = n - 1;
        boolean[] has = new boolean[n + 1];
        while (!ops.isEmpty()) {
            int[] op = ops.pop();
            int x = op[1];
            if (has[x]) continue;
            if (op[0] == 0) ans[l++] = x;
            else ans[r--] = x;
            has[x] = true;
        }
        for (int i = 1; i <= n; ++i) {
            if (!has[i]) ans[l++] = i;
        }
        for (int i = 0; i < n; ++i) System.out.print(ans[i] + " ");
    }
}