编程题
### 问题描述 你是一名年轻的密码学家,受聘于一家全球领先的安全技术公司——CyberSecurio。公司成功研发了一种高级密码锁系统,名为"CyberLock"。 "CyberLock" 密码锁系统的特殊之处在于,它将密码排列定义为 $1$ 到 $n$ 的一种排列。也就是说,每个元素在序列中只能出现一次,且取值范围是从 $1$ 到 $n$ 的整数。例如,对于长度为 $4$ 的密码序列,可能的排列之一是 $[2, 4, 3, 1]$,而 $[4, 1, 3, 2]$ 也是另一种合法排列。 我们可以对密码进行多次变换,一次变换的定义为交换相邻两个元素。密码的初始序列为 $a$,用户设置的密码为 $b$。只有用最小的变换次数使序列 $a$ 变换为序列 $b$,才能打开密码锁。 现在有了突发情况,有一位重要客户忘记了密码。幸运的是,在对系统日志进行深入分析后,你找到了当初设置密码时的初始序列 $a$。而客户现在只能记得密码应该是另一个合法的排列序列 $b$,但是忘记了如何操作。 为了帮助用户解开密码锁并顺利举办巡回展览,你需要找到从序列 $a$ 到序列 $b$ 的最小变换次数,以正确解开密码锁。 ### 输入格式 输入一共三行。 第 $1$ 行输入一个整数 $n$,表示密码排列的长度。 第 $2$ 行输入 $n$ 个整数,第 $i$ 个整数表示初始的密码序列 $a$ 的第 $i$ 个元素的价值 $a_i$。 第 $3$ 行输入 $n$ 个整数,第 $i$ 个整数表示设置的密码序列 $b$ 的第 $i$ 个元素的价值 $b_i$。 ### 输出格式 输出一行,这一行只包含一个整数,表示由初始的密码序列 $a$ 得到设置的密码序列 $b$ 的最小变换次数。 ### 样例输入 ```text 6 1 2 3 4 5 6 1 2 6 5 4 3 ``` ### 样例输出 ```text 6 ``` ### 样例说明 样例中的密码序列 $a$ 最少需要经过 $6$ 次变换才能得到密码序列$b$,例如: 第一步,$3$ 与 $4$ 交换 $\rightarrow$ $[1,2,4,3,5,6]$。 第二步,$3$ 与 $5$ 交换 $\rightarrow$ $[1,2,4,5,3,6]$。 第三步,$3$ 与 $6$ 交换 $\rightarrow$ $[1,2,4,5,6,3]$。 第四步,$4$ 与 $5$ 交换 $\rightarrow$ $[1,2,5,4,6,3]$。 第五步,$4$ 与 $6$ 交换 $\rightarrow$ $[1,2,5,6,4,3]$。 第六步,$5$ 与 $6$ 交换 $\rightarrow$ $[1,2,6,5,4,3]$。 所以结果为 $6$ 次。 ### 数据范围 对于 $50$% 的评测数据,$1 \le n \le 1000$。 对于所有评测数据,$1 \le n \le 10^6$,$1 \le a_i,b_i \le n$。
查看答案
赣ICP备20007335号-2