首页 > 试题广场 >

两个序列

[编程题]两个序列

热度指数：1417 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小强有两个序列 $\mathit a$ 和 $\mathit b$ ，这两个序列都是由相同的无重复数字集合组成的，现在小强想把 $\mathit a$ 序列变成 $\mathit b$ 序列，他只能进行以下的操作：
从序列 $\mathit a$ 中选择第一个或者最后一个数字并把它插入 $\mathit a$ 中的任意位置。
问小强至少需要几次操作可以将序列 $\mathit a$ 变为序列 $\mathit b$ 。

输入描述:

一行一个整数表示序列的长度。
接下来两行每行个整数。
第一行表示序列，第二行表示序列。



保证给出的序列符合题意。

输出描述:

输出一行一个整数表示答案。

示例1

输入

4
4 2 3 1
1 2 3 4

输出

算法知识视频讲解

CUG23届硕士毕业生

发表于 2022-04-13 12:46:04

看到互不相同的元素，一定想到hash！题目简述 n个互不相同的数，排列组合成两个序列a和b，每次操作只能从a中选择第一个或最后一个数字并插入a中任意位置，问最少需要多少次操作把a变成b。算法分析设n个元素为x1, x2, ..., xn，因为要从a变成b，所以把b中的值[xk1, xk2, . 展开全文

赫he

发表于 2023-05-16 10:57:59

将数组a中的数字变成和数组b中的数字顺序一样（两个序列都是由相同的无重复数字集合组成的），可以通过将每个唯一的数字映射到唯一的下标上。目标数组b中，记b[pos1]=b1,b[pos2]=b2,...,b[posj]=bj,...,b[posn]=bnb[pos_1]= b_1,b[pos_2]= 展开全文