题面描述:

给定两个长度为 $n$ 的整数数组 $nums1$ 和 $nums2$，可以通过交换数组 $nums2$ 中任意两个元素来使得所有下标 $i$ 满足 $nums1[i] = nums2[i]$，每次交换的代价为两个被交换元素下标的和。目标是计算使两个数组在对应位置相等的最小代价和，如果无法通过交换使两个数组相等，则返回 $-1$。输入格式为：第一行输入整数 $n$，表示数组的长度；第二行和第三行分别输入长度为 $n$ 的数组 $nums1$ 和 $nums2$。输出格式为满足要求的最小代价和，或无法满足时输出 $-1$。

思路:

记需要交换的总对数为 swapCount，其中要交换的数的众数为 modeValue，众数个数为 modeCount，我们分两种情况讨论：

1. 如果 modeCount <= swapCount / 2，即众数个数为总数的一半：

   • 如果 swapCount 为偶数，那么可以直接内部两两交换即可。
   • 如果 swapCount 为奇数，记为 2*k + 1，那么最极端的情况也是 k 个 a，k 个 b，1 个 c，这样才能拼成一个奇数且满足众数个数不超过总数一半。
   • 那么让 k - 1 个 a 和 k - 1 个 b 交换，剩下一个 a、b 和 c，那么至少有两个数可以和 nums1[0] 交换，剩下两个交换即可，依然可以内部解决。

2. 如果 modeCount > swapCount / 2，只需从前往后找不相等且不等于众数的数与众数交换，最后应满足 modeCount <= swapCount / 2。如不能满足则输出 -1。

代码详解

1. 变量定义：

   • swapCount：需要交换的元素总个数，即满足 nums1[i] == nums2[i] 的那些元素。
   • modeCount：记录当前众数的数量。
   • modeValue：当前的众数，即出现最多的数。

2. 第一遍遍历数组：

   • 统计哪些元素需要被交换（即 nums1[i] == nums2[i] 的那些元素）。
   • 更新这些元素的出现次数，并确定当前的众数和众数的数量。

3. 第二遍遍历数组：

   • 如果众数的数量超过了总交换数的一半，需要逐步处理不等于众数的元素，尝试与众数进行交换，直到众数的个数不再超过总数的一半。

4. 输出结果：

   • 如果通过交换不能满足要求（即 modeCount > swapCount / 2），则输出 -1。
   • 否则，输出最小的交换代价 totalCost。

#include <bits/stdc++.h>
using namespace std;

const int MAX_SIZE = 1e5 + 10;
int nums1[MAX_SIZE], nums2[MAX_SIZE];
int swapCount; // 需要交换的元素总数
int modeCount; // 众数的个数
int countMap[MAX_SIZE]; // 记录每个数的个数
int modeValue; // 众数的值

signed main() {
    int n;
    cin >> n; // 输入数组的长度
    for (int i = 0; i < n; i++) cin >> nums1[i]; // 输入第一个数组
    for (int i = 0; i < n; i++) cin >> nums2[i]; // 输入第二个数组

    int totalCost = 0; // 记录总交换代价

    // 统计冲突的元素
    for (int i = 0; i < n; i++) {
        if (nums1[i] == nums2[i]) {
            totalCost += i; // 当前索引的代价
            ++swapCount; // 需要交换的总数增加
            ++countMap[nums1[i]]; // 统计当前元素的个数

            // 更新众数和众数个数
            int currentValue = nums1[i];
            if (countMap[currentValue] > modeCount) {
                modeCount = countMap[currentValue];
                modeValue = currentValue;
            }
        }
    }

    // 处理冲突的元素
    for (int i = 0; i < n && modeCount * 2 > swapCount; i++) {
        int a = nums1[i], b = nums2[i];
        // 交换众数与其他不同的元素
        if (a != b && a != modeValue && b != modeValue) {
            totalCost += i; // 计算交换代价
            ++swapCount; // 需要交换的总数增加
        }
    }

    // 判断是否能满足条件
    if (modeCount * 2 > swapCount) {
        cout << -1 << endl; // 无法满足条件
    } else {
        cout << totalCost << endl; // 输出总交换代价
    }

    return 0;
}

题目内容

给定 $2$ 个长度为均为 $n$ 的整数数组 $nums1$ 和 $nums2$ ，每次操作可以交换数组 $nums2$ 中任意 $2$ 个元素，其代价为两个下标的和。

目标是对于所有的下标 $i$ 。$0<=i<n$ ，$n$ 为数组的长度，都满足$nums1[i] \neq nums2[i]$。

返回满足目标的最小代价和，如果达不成目标，返回 $-1$ 。

输入描述

输入格式:

第一行输入整数数组的长度 $n$

第二行输入长度为 $n$ 的整数数组 $nums1$

第二行输入长度为 $n$ 的整数数组 $nums2$

$1 <=n <= 10^5$

$1 <= nums1[i],nums2[i]<=10^5$

输出描述

样例1

输入

4
1 2 3 4
1 2 3 4

输出

6

说明

其中代价和最小的一种方法为:

交换下标为 $0$ 和 $1$ 的两个值，代价为 $0+1=1$ ，现在 $nums1=[2,1,3,4]$ 。

交换下标为 $2$ 和 $3$ 的两个值，代价为 $2+3=5$ ，现在 $nums1=[2,1,4,3]$。

总代价为 $6$ 。

样例2

输入

3
2 1 1
1 1 2

输出

-1

说明

无论怎么操作，都无法要求。所以返回 $-1$ 。