目录

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 种之一:

左移

x

x

x, 即把

x

x

x 移动到最左边。 右移

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的范围这时间复杂度显然是不可接受的。想要解决此题我们需要思考两个点:

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

  对于第一点，我们应该快速地想到链表这个数据结构，由于题目需要在左端点和右端点都进行插入操作，所以我们应该联想到 双链表 。它可以在

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 <=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++

#include

using namespace std;

typedef long long LL;

typedef unsigned long long uLL;

typedef pair 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 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 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;

}

查看原文