คำชี้แจงปัญหา
กำหนดอาร์เรย์สองชุดที่มีขนาดเท่ากัน 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
