← 返回题目列表

Codeforces · 2062/G

G. 排列工厂

中文机器翻译题面 查看原题

给你两个排列 $$$p_1,p_2,\ldots,p_n$$$ 和 $$$q_1,q_2,\ldots,q_n$$$,长度为 $$$n$$$。在一次操作中,您可以选择两个整数 $$$1\leq i,j\leq n,i\neq j$$$ 并交换 $$$p_i$$$ 和 $$$p_j$$$。该操作的成本为$$$\min (|i-j|,|p_i-p_j|)$$$。

找到使 $$$p_i = q_i$$$ 对于所有 $$$1\leq i\leq n$$$ 成立的最小成本,并输出实现最小成本的操作序列。

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

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 输入测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 100$$$) — 排列 $$$p$$$ 和 $$$q$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$p_1,p_2,\ldots,p_n$$$ ($$$1\leq p_i\leq n$$$) — 排列 $$$p$$$。保证 $$$p_1,p_2,\ldots,p_n$$$ 是 $$$1,2,\ldots,n$$$ 的排列。

第三行包含 $$$n$$$ 整数 $$$q_1,q_2,\ldots,q_n$$$ ($$$1\leq q_i\leq n$$$) — 排列 $$$q$$$。保证 $$$q_1,q_2,\ldots,q_n$$$ 是 $$$1,2,\ldots,n$$$ 的排列。

保证所有测试用例的$$$n^3$$$总和不超过$$$10^6$$$。

输出

对于每个测试用例,在第一行输出操作总数 $$$k$$$ ($$$0\le k\le n^2$$$)。然后输出 $$$k$$$ 行,每行包含两个整数 $$$i,j$$$ ($$$1\le i,j\le n$$$, $$$i\neq j$$$) 表示按顺序交换 $$$p_i$$$ 和 $$$p_j$$$ 的操作。

可以证明最优操作序列的长度不大于$$$n^2$$$。

示例

输入 #1

4
2
2 1
2 1
3
1 2 3
3 2 1
4
2 1 4 3
4 2 3 1
5
1 4 3 2 5
5 2 3 4 1

输出 #1

0
1
1 3
3
1 4
2 4
1 3
4
1 2
4 5
2 5
1 4

注意

在第二个测试用例中,您可以交换 $$$p_1,p_3$$$,成本为 $$$\min(|1-3|,|1-3|)=2$$$。那么 $$$p$$$ 等于 $$$q$$$,成本为 $$$2$$$。

在第三个测试用例中,您可以执行以下操作:

最初,$$$p=[2,1,4,3]$$$。

1. 交换$$$p_1,p_4$$$,成本为$$$\min(|1-4|,|2-3|)=1$$$,得到$$$p=[3,1,4,2]$$$。
2. 交换$$$p_2,p_4$$$,成本为$$$\min(|2-4|,|1-2|)=1$$$,得到$$$p=[3,2,4,1]$$$。
3. 交换 $$$p_1,p_3$$$ 成本 $$$\min(|1-3|,|3-4|)=1$$$。那么 $$$p$$$ 等于 $$$q$$$,成本为 $$$3$$$。