题解 | #最佳配对#

解题思路

这是一道关于数组匹配的题目，主要思路如下：

1. 给定两个长度为 的数组 和 ，需要修改 中的一个元素
2. 当 时，认为 是一个配对
3. 每个元素最多只能在配对集合中出现一次
4. 目标是通过修改 中的一个元素，使得最佳配对集合的元素最多

解题步骤：

1. 首先统计当前能配对的数量
2. 如果已经完全配对 ，则需要减少一个配对以便修改
3. 如果未完全配对，则修改后可以增加一个配对
4. 输出最终的配对数量

代码

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[10] = {0}, b[10] = {0};
    
    // 输入数组A和B
    for(int i = 0; i < n; i++)
        cin >> a[i];
    for(int i = 0; i < n; i++)
        cin >> b[i];
    
    // 计算当前配对数量
    int k = 0;
    bool used[10] = {false};
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(a[i] == b[j] && !used[j]) {
                k++;
                used[j] = true;
                break;
            }
        }
    }
    
    // 根据配对情况调整结果
    if(k == n)
        k--;
    else
        k++;
        
    cout << k << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        
        // 输入数组
        for(int i = 0; i < n; i++)
            a[i] = sc.nextInt();
        for(int i = 0; i < n; i++)
            b[i] = sc.nextInt();
            
        // 计算配对数量
        int k = 0;
        boolean[] used = new boolean[n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(a[i] == b[j] && !used[j]) {
                    k++;
                    used[j] = true;
                    break;
                }
            }
        }
        
        // 输出结果
        if(k == n)
            k--;
        else
            k++;
            
        System.out.println(k);
    }
}

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

# 计算当前配对数量
k = 0
used = [False] * n
for i in range(n):
    for j in range(n):
        if a[i] == b[j] and not used[j]:
            k += 1
            used[j] = True
            break

# 根据配对情况调整结果
if k == n:
    k -= 1
else:
    k += 1

print(k)

算法及复杂度

• 算法：贪心匹配
• 时间复杂度： - 需要遍历所有可能的配对
• 空间复杂度： - 需要存储两个数组和访问标记数组