Swaps
题意翻译
给出两个长度为 $n$ 的序列 $a$, $b$,序列 $a$ 中的元素是 $[1,2n]$ 中的 **奇数**,序列 $b$ 的元素是 $[1,2n]$ 中的 **偶数**。
现可对两个序列进行操作,每次操作的步骤如下:
- 选取任意一个序列 $a$ 或 $b$
- 选取一个下标 $i \;\; (i \in [1, n-1])$
- 将选定序列的下标为 $i$ 的元素与下标为 $(i+1)$ 的元素交换
问最少经过多少次操作,使得序列 $a$ 的字典序小于序列 $b$ ?
Tips:对于相同的两个不同序列 $x$ 和 $y$ ,如果在 $x$ 和 $y$ 元素值不同的第一个位置,序列 $x$ 的元素比 $y$ 中的对应的元素小,那么我们说 $x$ 的字典序小于 $y$ 。
样例解释:
对于第一个样例,序列 $a$ 的字典序已经小于了 $b$,故无需操作;
对于第二个样例,可选择交换 $5$ 和 $3$,再交换 $2$ 和 $4$,分别得到新序列 $[3, 5, 1]$ 和 $[4, 2, 6]$,此时满足题意且操作数最少;但操作数最少的方案可能不止一种。
题目描述
You are given two arrays $ a $ and $ b $ of length $ n $ . Array $ a $ contains each odd integer from $ 1 $ to $ 2n $ in an arbitrary order, and array $ b $ contains each even integer from $ 1 $ to $ 2n $ in an arbitrary order.
You can perform the following operation on those arrays:
- choose one of the two arrays
- pick an index $ i $ from $ 1 $ to $ n-1 $
- swap the $ i $ -th and the $ (i+1) $ -th elements of the chosen array
Compute the minimum number of operations needed to make array $ a $ lexicographically smaller than array $ b $ .For two different arrays $ x $ and $ y $ of the same length $ n $ , we say that $ x $ is lexicographically smaller than $ y $ if in the first position where $ x $ and $ y $ differ, the array $ x $ has a smaller element than the corresponding element in $ y $ .
输入输出格式
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ).
The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the length of the arrays.
The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 2n $ , all $ a_i $ are odd and pairwise distinct) — array $ a $ .
The third line of each test case contains $ n $ integers $ b_1, b_2, \ldots, b_n $ ( $ 1 \le b_i \le 2n $ , all $ b_i $ are even and pairwise distinct) — array $ b $ .
It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .
输出格式
For each test case, print one integer: the minimum number of operations needed to make array $ a $ lexicographically smaller than array $ b $ .
We can show that an answer always exists.
输入输出样例
输入样例 #1
3
2
3 1
4 2
3
5 3 1
2 4 6
5
7 5 9 1 3
2 4 6 10 8
输出样例 #1
0
2
3
说明
In the first example, the array $ a $ is already lexicographically smaller than array $ b $ , so no operations are required.
In the second example, we can swap $ 5 $ and $ 3 $ and then swap $ 2 $ and $ 4 $ , which results in $ [3, 5, 1] $ and $ [4, 2, 6] $ . Another correct way is to swap $ 3 $ and $ 1 $ and then swap $ 5 $ and $ 1 $ , which results in $ [1, 5, 3] $ and $ [2, 4, 6] $ . Yet another correct way is to swap $ 4 $ and $ 6 $ and then swap $ 2 $ and $ 6 $ , which results in $ [5, 3, 1] $ and $ [6, 2, 4] $ .