题面描述:

给定两个长度为 $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。

cpp

#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;
}

python

# 定义常量和初始化数组
MAX_SIZE = int(1e5 + 10)
nums1 = [0] * MAX_SIZE
nums2 = [0] * MAX_SIZE
swapCount = 0  # 需要交换的数的总个数
modeCount = 0   # 记录当前众数的个数
countMap = [0] * MAX_SIZE  # 记录每个数的出现次数
modeValue = 0  # 当前的众数

# 输入数组长度和元素
n = int(input())
nums1 = list(map(int, input().split()))
nums2 = list(map(int, input().split()))

totalCost = 0  # 记录总交换代价

# 第一遍遍历数组，统计需要交换的元素
for i in range(n):
    if nums1[i] == nums2[i]:
        totalCost += i  # 计算交换代价
        swapCount += 1  # 交换总数增加
        countMap[nums1[i]] += 1  # 记录当前元素的出现次数
        currentValue = nums1[i]  # 当前元素值
        
        # 更新众数和众数的个数
        if countMap[currentValue] > modeCount:
            modeCount = countMap[currentValue]
            modeValue = currentValue

# 第二遍遍历数组，处理众数
for i in range(n):
    if modeCount * 2 <= swapCount:
        break  # 如果众数个数不超过总数的一半，结束处理

    a = nums1[i]
    b = nums2[i]
    
    # 交换不等于众数的元素
    if a != b and a != modeValue and b != modeValue:
        totalCost += i  # 计算交换代价
        swapCount += 1  # 交换总数增加

# 输出结果
if modeCount * 2 > swapCount:
    print(-1)  # 无法满足条件
else:
    print(totalCost)  # 输出总交换代价

java

import java.util.Scanner;

public class Main {
    public static final int MAX_SIZE = (int) 1e5 + 10;
    public static int[] nums1 = new int[MAX_SIZE];
    public static int[] nums2 = new int[MAX_SIZE];
    public static int swapCount = 0; // 需要交换的元素总个数
    public static int modeCount = 0; // 当前众数的个数
    public static int[] countMap = new int[MAX_SIZE]; // 记录每个数的出现次数
    public static int modeValue = 0; // 当前的众数

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 输入数组长度

        // 输入第一个数组
        for (int i = 0; i < n; i++) {
            nums1[i] = sc.nextInt();
        }
        // 输入第二个数组
        for (int i = 0; i < n; i++) {
            nums2[i] = sc.nextInt();
        }

        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];
            int b = nums2[i];
            // 交换不等于众数的元素
            if (a != b && a != modeValue && b != modeValue) {
                totalCost += i; // 计算交换代价
                swapCount++; // 交换总数增加
            }
        }

        // 输出结果
        if (modeCount * 2 > swapCount) {
            System.out.println(-1); // 无法满足条件
        } else {
            System.out.println(totalCost); // 输出总交换代价
        }

        sc.close(); // 关闭输入流
    }
}

题目内容

给定 $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$ 。