题目内容

你有两个长度均为 $n$ 的整数数组 $nums1$ 和 $nums2$，数组下标从 0 开始。允许对 $nums2$ 执行任意多次操作。一次操作定义为：选择两个不同的下标 $i$ 和 $j$，交换 $nums2[i]$ 与 $nums2[j]$，该次操作的代价为 $i+j$。

操作结束后，需要保证对每个下标 $i$ 都满足 $nums1[i] e nums2[i]$。请计算达成这一目标所需的最小总代价。如果无论如何操作都无法满足条件，则输出 -1。

约束条件

• 数组长度 $n$ 满足 $1 \le n \le 10^5$。
• $nums1$ 和 $nums2$ 中的元素均为整数，且满足 $1 \le nums1[i], nums2[i] \le 10^5$。

输入描述

第一行包含一个整数 $n$，表示两个数组的长度。

第二行包含 $n$ 个整数，依次表示数组 $nums1$ 中的元素。

第三行包含 $n$ 个整数，依次表示数组 $nums2$ 中的元素。

输出描述

输出一个整数，表示达成目标所需的最小总代价；若无法达成目标，则输出 -1。

样例1

输入

3
1 2 3
1 2 3

输出

3

说明

三个位置均冲突，冲突值分别为 1、2、3，均只出现一次，没有超过冲突总数 3 的一半。

参与交换的下标为 0、1、2，总代价为 $0+1+2=3$。一种可行方案是：先交换下标 0 和 1，代价 $0+1=1$；再交换下标 0 和 2，代价 $0+2=2$。最终 nums2 变为 [3,1,2]，与 nums1 的每个位置均不同，因此总代价为 3。

样例2

输入

1
5
5

输出

-1

说明

唯一位置 0 处的元素相同，发生冲突。

由于数组长度 $n=1$，无法选择两个不同下标进行交换，因此无法达成目标，输出 -1。

样例3

输入

4
1 1 2 3
1 1 2 4

输出

6

说明

初始冲突位置为 0、1、2，对应冲突值为 1、1、2，其中值 1 出现 2 次，超过冲突总数 3 的一半。

因此需要额外引入非冲突位置 3，该位置满足 $nums1[3]=3$、$nums2[3]=4$，均不等于众数 1。

参与交换的下标为 0、1、2、3，总代价为 $0+1+2+3=6$。一种可行方案是：交换下标 0 和 2（代价 $0+2=2$），再交换下标 1 和 3（代价 $1+3=4$），总代价为 $2+4=6$。最终 nums2 变为 [2,4,1,1]，所有位置满足 $nums1[i] e nums2[i]$，因此输出 6。

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写