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

这篇具有很好参考价值的文章主要介绍了第十三届蓝桥杯Java B 组国赛 C 题——左移右移(AC)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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. 1N,M200000,1xN.

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 l1 ,若要将其移动最右边则将其赋值为 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<Integer,Node> 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 <=n; 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 < m; i++) {
            char c=sc.next().charAt(0);
            int x=sc.nextInt();
            //先将x对应的结点在双链表中删除
            Node node=map.get(x);
            node.pre.next=node.next;
            node.next.pre=node.pre;
            if (c=='L'){
                //将其插入到左端点
                node.next=head.next;
                head.next.pre=node;
                head.next=node;
                node.pre=head;
            }else{
                //将其插入到右端点
                node.pre=last.pre;
                last.pre.next=node;
                node.next=last;
                last.pre=node;
            }
        }
        pre=head.next;
        while (pre!=last){
            out.print(pre.v+" ");
            pre=pre.next;
        }
        out.flush();
    }
    static class Node{
        int v;
        Node pre;
        Node next;
        public Node(int v, Node pre, Node next) {
            this.v = v;
            this.pre = pre;
            this.next = next;
        }
    }
}

C++文章来源地址https://www.toymoban.com/news/detail-788366.html

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 200010;

int n, m;
void solve()
{
	cin >> n >> m;
	std::vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		a[i] = i;
	}
	int l = 0, r = n - 1;
	string op;
	int x;
	for (int i = 0; i < m; ++i) {
		cin >> op >> x;
		x--;
		if (op == "L") a[x] = --l;
		else a[x] = ++r;
	}
	std::vector<PII> b(n);
	for (int i = 0; i < n; ++i) {
		b[i] = {a[i], i};
	}
	sort(all(b));
	for (auto [x, y]: b) cout << y + 1 << " ";
}
int main()
{
	ios_base :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t = 1;
	while (t--)
	{
		solve();
	}
	return 0;
}

到了这里,关于第十三届蓝桥杯Java B 组国赛 C 题——左移右移(AC)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 蓝桥杯第十三届单片机国赛程序

    写在前面: 做完总体来说感觉一年比一年难了(估计是被骂的),虽然十三届用的底层少,但是做起来困难重重。 最难的难点在于定时器安排问题。15F2K60S2系列单片机只有三个定时器,本届题目考到了频率测量、超声波、PWM输出,再加上刷新,每一个都需要一个定时器,比

    2024年02月08日
    浏览(50)
  • 蓝桥杯单片机第十三届国赛客观题(深夜学习——单片机)

    1.填空题 (2)不同的地址范围: data:0x00-0xff idata:0x0000-0xffff xdata:0x0000-0xffff pdata:0x00-0xff code:0x0000-0xffff 2.选择题 (3)模电——》多级放大电路 (6)DS18B20 (7)模电——》二极管  (8)单片机      

    2024年02月11日
    浏览(63)
  • 第十三届蓝桥杯国赛 Web 前端组(大学组) 真题练习及答案解析

    考点:数组方法 思路:利用splice()方法 考点:flex布局 思路:照着写就行 考点: DOM 操作 思路:1 先做需求:隐藏开始按钮,方格上的图片显示后又隐藏。 2 再做第一次点击图片翻转效果。 3 做第二次点击的逻辑判断,若水果相同则,进行消除,加分操作,水果不同,进行隐

    2024年02月06日
    浏览(57)
  • 【蓝桥杯嵌入式】第十三届蓝桥杯嵌入式国赛程序设计试题以及详细题解

      本届国赛试题主要包含 LCD 、 LED 、 按键 、 EEPROM 、 串口 、 模拟电压输入 、 脉冲输入输出 七大部分,其中前面三个部分是蓝桥杯嵌入式的“亲儿子”(必考部分),而剩下的四个部分都为“干儿子”(考频相对较高)。   相对于本届省赛两套试题:   本套试题 串口数

    2024年02月02日
    浏览(84)
  • 2022 第十三届蓝桥杯大赛软件赛决赛, 国赛,C/C++ 大学B组题解

    2022 第十三届蓝桥杯大赛软件赛决赛, 国赛,C/C++ 大学B组题解 补题链接:地址 两个填空题说实话感觉非常花时间。 第1题 —— 2022 (5分) 题意:将2022拆成10个数相加,有多少方案。 思路:划分dp经典题,数字i划分成j个数。 答案:379187662194355221 第2题 —— 钟表 (5分) 题意

    2024年02月04日
    浏览(45)
  • 第十三届蓝桥杯嵌入式国赛真题(基于HAL库的巨简代码+超级详解)

    相关说明: 开发板:CT117E-M4(STM32G431RBT6) 开发环境: CubeMX+Keil5 涉及题目:第十三届蓝桥杯嵌入式国赛真题 难点:双路AD测量电压、输入捕获测频率、LCD屏幕翻转、冒泡法、初始上电判断、按键长短按 CubeMX配置、主要函数代码及说明: 1.使能外部高速时钟: 2.配置时钟树:

    2023年04月09日
    浏览(68)
  • 第十三届蓝桥杯省赛与国赛真题题解大汇总(十四届参赛者必备)

      大家好,我是执梗。本文汇总了我写的第十三届蓝桥杯所有省赛真题与国赛真题,会针对每道题打出我自己的难度评星⭐️,也会给出每道题的算法标签,帮助大家更有针对性的去学习和准备,当然许多题目由于难度或时间的原因暂未更新,如果有不懂的问题也可以在评

    2024年02月11日
    浏览(75)
  • 第十三届蓝桥杯国赛 C++ C 组 Java A 组 C 组 Python C 组 E 题——斐波那契数组(三语言代码AC)

    如果数组 A = ( a 0 , a 1 , ⋯ . a n − 1 ) A=(a_0,a_1,⋯.a_{n-1}) A = ( a 0 ​ , a 1 ​ , ⋯ . a n − 1 ​ ) 满足以下条件, 就说它是一个斐波那契数组: n ≥ 2 ; n≥2; n ≥ 2 ; a 0 = a 1 a_0=a_1 a 0 ​ = a 1 ​ 对于所有的 i ( i ≥ 2 ) , i(i≥2), i ( i ≥ 2 ) , 都满足 a i = a i − 1 + a i − 2 。 a_i=a_{i-1}+a_{i-2

    2024年01月18日
    浏览(42)
  • 第十三届蓝桥杯国赛 C++ C组 F 题、Python B组 E 题——近似GCD(AC)

    小蓝有一个长度为 n n n 的数组 A = ( a 1 , a 2 , ⋯   , a n ) A=left(a_{1}, a_{2}, cdots, a_{n}right) A = ( a 1 ​ , a 2 ​ , ⋯ , a n ​ ) , 数组的子数组被定义为从 原数组中选出连续的一个或多个元素组成的数组。数组的最大公约数指的是数 组中所有元素的最大公约数。如果最多更改数组

    2024年01月16日
    浏览(43)
  • 2020第十一届蓝桥杯Python组国赛【真题+解析+代码】

    🚀 真题练习,冲刺国赛 🚀 2020年第十一届蓝桥python组国赛真题+解析+代码 博观而约取,厚积而薄发 🏆 国赛真题目录 🍰1.题目 美丽的2 👑2.思路分析 难度:⭐️ 标签:枚举字符串 🎇 思路:暴力法 🔱 思路分析: 本题为填空题,只需要遍历 1 → 2020 1→2020 1 → 2020 即可:

    2024年02月07日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包