第十三届蓝桥杯Java B 组国赛 C 题——左移右移（AC）

目录

• 1.左移右移
• • 1.题目描述
  • 2.输入格式
  • 3.输出格式
  • 4.样例输入
  • 5.样例输出
  • 6.数据范围
  • 6.原题链接
  • 2.解题思路
  • 3.Ac_code

    1.左移右移

    1.题目描述

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

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

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

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

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

    2.输入格式

    第一行包含 2 个整数, N N N 和 M M M 。以下 M M M 行每行一个操作, 其中 “ L x Lx Lx "表示左移 x x x ," R x Rx Rx "表示右移 x x x 。

    3.输出格式

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

    4.样例输入

    5 3

    
    （图片来源网络，侵删）

    L 3

    L 2

    R 1

    5.样例输出

    2 3 4 5 1

    6.数据范围

    1 ≤ N , M ≤ 200000 , 1 ≤ x ≤ N . 1≤N,M≤200000,1≤x≤N. 1≤N,M≤200000,1≤x≤N.

    6.原题链接

    左移右移

    2.解题思路

      题目的含义非常简单，如果按照朴素的方式遍历寻找 x x x，然后直接进行插入操作，在 n n n的级别在 2 e 5 2e5 2e5的范围这时间复杂度显然是不可接受的。想要解决此题我们需要思考两个点:

    1. 如何高效地进行插入和删除操作
    2. 如何快速地找到某个点所在的位置

      对于第一点，我们应该快速地想到链表这个数据结构，由于题目需要在左端点和右端点都进行插入操作，所以我们应该联想到 双链表 。它可以在 O ( 1 ) O(1) O(1)的时间范围内对元素进行插入和删除，这显然是我们需要的数据结构。

      当然，双链表并不支持高效地查找，所以我们如何快速找到 x x x 的位置呢？这时候我们应该联想到 哈希表，因为我们需要手动实现双链表，所以每个链表结点都对应一个值，同时它也是一个对象，我们可以使用哈希表，以值为 k e y key key，以这个链表结点对象为 v a l u e value value。这样我们就可以快速获得这个结点，然后再进行常规的双链表插入删除操作。

    考虑一个更简单的做法，由于每次都将某个数要么变为最大，要么变为最小，那么我们可以记录每个数的权值大小。假设此时最小的数权值为 l l l ，最大的数权值为 r r r ，若要将 x x x 挪到最左边，将其权值赋值为 l − 1 l-1 l−1 ，若要将其移动最右边则将其赋值为 r + 1 r+1 r+1，同时更新 l , r l,r l,r。每个数最开始的权值等于其自身，当操作完毕后，按照权值排序得到的序列即是答案。

    3.Ac_code

    Java

    
    （图片来源网络，侵删）

    import java.io.OutputStreamWriter;
    import java.io.PrintWriter;
    import java.util.*;
    public class Main {
        static Map map=new HashMap();
        static PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
        public static void main(String[] args) {
            Scanner sc=new Scanner(System.in);
            int n=sc.nextInt();
            int m=sc.nextInt();
            //双链表的头结点和尾结点
            Node head=new Node(-1,null,null);
            Node last=new Node(-1,null,null);
            Node pre=head;
            //构建双链表
            for (int i = 1; i 
                pre.next=new Node(i,pre,null);
                pre=pre.next;
                map.put(i,pre);
            }
            last.pre=pre;
            pre.next=last;
            for (int i = 0; i  n >> m;
    	std::vector a(n);
    	for (int i = 0; i > op >> x;
    		x--;
    		if (op == "L") a[x] = --l;
    		else a[x] = ++r;
    	}
    	std::vector b(n);
    	for (int i = 0; i