seuOJ445 - 不相似度

题目类型：传统
输入文件：标准输入流
输出文件：标准输出流
时间限制：1000 ms
空间限制：256 MiB
题目标签：短码, 初赛, 2023

题目描述

给定两个长度为 $n$ 的排列 $\{P_n\},\{Q_n\}$ 。定义 $P_{idx,i}$ 为数字 $i$ 在排列 $\{P_n\}$ 中出现的下标， $Q_{idx,i}$ 为数字 $i$ 在排列 $\{Q_n\}$ 中出现的下标。

对于 $\forall i\in[1,n]$ ，定义 $i$ 在排列 $\{P_n\},\{Q_n\}$ 之间的距离 $dis(i,P_n,Q_n)$ 为 $|P_{idx,i}-Q_{idx,i}|$ 。我们称排列 $\{P_n\},\{Q_n\}$ 的不相似度为所有数字在两个排列之间的距离之和，即 $\sum_{i=1}^n dis(i,P_n,Q_n)$ 。

现在，你可以在排列 $\{Q_n\}$ 中任选两个元素（可以相同），并交换它们的位置，并使得交换后排列 $\{P_n\},\{Q_n\}$ 之间的不相似度最小。

请输出交换后最小的不相似度。

一个长度为 $n$ 的排列是由 $n$ 个从 $1$ 到 $n$ 的不同整数以任意顺序组成的数组。例如， $[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是一个排列（ $2$ 在数组中出现两次）， $[1,3,4]$ 也不是一个排列（ $n=3$ 但数组中有 $4$ ）。

输入格式

第一行一个正整数 $n(1\le n \le 3000)$ ，表示排列的长度。

接下来一行，用空格隔开的 $n$ 个正整数，表示排列 $\{P_n\}$ 。

接下来一行，用空格隔开的 $n$ 个正整数，表示排列 $\{Q_n\}$ 。

保证 $1\le P_i,Q_i\le n$ ，且每个数字在 $\{P_n\},\{Q_n\}$ 中只出现一次。

输出格式

输出一个非负整数，表示交换后最小的不相似度。

样例

输入样例 1：

5
1 2 3 4 5
1 2 3 4 5

输出样例 1：

输入样例 2：

5
5 4 3 2 1
1 2 3 4 5

输出样例 2：