侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

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

GabrielxD
2023-02-05 / 0 评论 / 0 点赞 / 257 阅读 / 729 字
温馨提示:
本文最后更新于 2023-02-05,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

左移右移 - 蓝桥云课


问题描述

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

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

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

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

输入格式

第一行包含 2 个整数, NNMM

以下 MM 行每行一个操作, 其中 "L x" 表示左移 xx"R x" 表示右移 xx

输出格式

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

样例输入

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][1,2,3,4,5]→[3,1,2,4,5]→[2,3,1,4,5]→[2,3,4,5,1]

评测用例规模与约定

对于 5050% 的评测用例, 1N,M100001 \le N, M \le 10000

对于 100100% 的评测用例, 1,N,M,200000,1xN1 \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] + " ");
    }
}
0
博主关闭了所有页面的评论