1294: 让数组不相等的最小总代价

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:0 通过:0 通过率:NAN%

题目描述

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ,两者长度都为 n 。
每次操作中,你可以选择交换 nums1 中任意两个下标处的值。操作的 开销 为两个下标的 和 。
你的目标是对于所有的 0 <= i <= n - 1 ,都满足 nums1[i] != nums2[i] ,你可以进行 任意次 操作,请你返回达到这个目标的 最小 总代价。
请你返回让 nums1 和 nums2 满足上述条件的 最小总代价 ,如果无法达成目标,返回 -1 。

输入格式

输入第一行为两个整数 n 代表数组的长度。
接下来两个输入两个数组。

输出格式

输出结果为一个整数。

输入样例 复制

5
1 2 3 4 5
1 2 3 4 5

输出样例 复制

10

数据范围与提示

实现目标的其中一种方法为:
- 交换下标为 0 和 3 的两个值,代价为 0 + 3 = 3 。现在 nums1 = [4,2,3,1,5] 。
- 交换下标为 1 和 2 的两个值,代价为 1 + 2 = 3 。现在 nums1 = [4,3,2,1,5] 。
- 交换下标为 0 和 4 的两个值,代价为 0 + 4 = 4 。现在 nums1 = [5,3,2,1,4] 。
最后,对于每个下标 i ,都有 nums1[i] != nums2[i] 。总代价为 10 。
还有别的交换值的方法,但是无法得到代价和小于 10 的方案。
1 <= n <= 105
1 <= nums1[i], nums2[i] <= n