在C ++中最大化两个数组中的唯一对

问题陈述

给定两个大小为N的数组，使用它们的元素形成最大对数，一个来自第一个数组，第二个来自第二个数组，这样每个数组中的一个元素最多使用一次，并且所选元素之间的绝对差用于形成一对的元素小于或等于给定元素K。

示例

如果输入为-

arr1[]={3，4，5，2，1}

arr2[]={6，5，4，7，15}

并且k=3，那么我们可以形成以下4对绝对差小于或等于3的对-

(1,4)，(2,5)，(3,6)，(4,7)

算法

我们可以使用递归方法来解决这个问题

对两个数组进行排序

如果可能形成一对，则将第一个数组的每个元素与第二个数组的每个元素进行比较

继续检查第一个数组的下一个元素的下一个可能对。

示例

现在让我们看一个例子-

#include <bits/stdc++.h> using namespace std; int getMaxUniquePairs(int *arr1, int *arr2, int n, int k) { sort(arr1, arr1 + n); sort(arr2, arr2 + n); bool visited[n]; memset(visited, false, sizeof(visited)); int pairCnt = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (abs(arr1[i] - arr2[j]) <= k && visited[j] == false) { ++pairCnt; visited[j] = true; break; } } } return pairCnt; } int main() { int arr1[] = {3, 4, 5, 2, 1}; int arr2[] = {6, 5, 4, 7, 15}; int n = sizeof(arr1) / sizeof(arr1[0]); int k = 3; cout << "Maximum unique pairs = " << getMaxUniquePairs(arr1, arr2, n, k) << endl; return 0; }

输出结果

Maximum unique pairs = 4