第十三届蓝桥杯大赛软件类决赛Java大学B组C题——左移右移解题思路

65 阅读 0 评论 43 点赞

我是靠谱客的博主无奈夕阳，最近开发中收集的这篇文章主要介绍第十三届蓝桥杯大赛软件类决赛Java大学B组C题——左移右移解题思路，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

【问题描述】
小蓝有一个长度为 N 的数组，初始时从左到右依次是 1, 2, 3, . . . N。
之后小蓝对这个数组进行了 M 次操作，每次操作可能是以下 2 种之一：

左移 x，即把 x 移动到最左边。
右移 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
【样例说明】
样例中的数组变化如下：
试题 C: 左移右移 4
第十三届蓝桥杯大赛软件赛决赛 Java 大学 B 组
[1, 2, 3, 4, 5] → [3, 1, 2, 4, 5] → [2, 3, 1, 4, 5] → [2, 3, 4, 5, 1]
【评测用例规模与约定】
对于 50% 的评测用例，1 ≤ N, M ≤ 10000.
对于 100% 的评测用例，1 ≤ N, M ≤ 200000, 1 ≤ x ≤ N.

解题思路

我们可以把每一个数字放入一个map集合中，自己作为key，把value当成权重值，默认为这个数字本身。每一个左移右移修改对应的权重值，最后根据权重值来排序。

可以设置一个最左边界的临界值 L=0，每进行一次左移操作，把这个元素相对的权重值改为最左临界值，再把临界值进行自减操作。

同理，设置一个最右边界的临界值R=n+1，每进行一次右移操作，把这个元素相对的权重值改为最右临界值，再把临界值进行自增操作。

在这里插入图片描述

Java代码（AC）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        String[] num = br.readLine().split(" ");
        int n=Integer.parseInt(num[0]);
        int m=Integer.parseInt(num[1]);
        int l=0,r=n+1;
        HashMap<Integer,Integer> map=new HashMap<>();
        for (int i=1;i<=n;i++){
            map.put(i,i);
        }
        while (m>0){
            String[] s = br.readLine().split(" ");
            if (s[0].equals("L")){
                map.put(Integer.parseInt(s[1]),l--);//每次左移之后。临界值就要自减。因为后续是根据value值来排序的
            }else {
                map.put(Integer.parseInt(s[1]),r++);//每次右移之后。临界值就要自增
            }
            m--;
        }
        List<Map.Entry<Integer,Integer>> list=new ArrayList<Map.Entry<Integer,Integer>>(map.entrySet());
        //把map集合根据value排序
        Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o1.getValue()-o2.getValue();
            }
        });
        for (Map.Entry<Integer, Integer> mapping : list) {
            System.out.print(mapping.getKey()+" ");
        }
    }
}