คำชี้แจงปัญหา
คุณจะได้รับอาร์เรย์ของจำนวนเต็ม n และจำนวนเต็ม K ค้นหาจำนวนคู่ที่ไม่เรียงลำดับทั้งหมด {i, j} เพื่อให้ค่าสัมบูรณ์ของ |ai + aj – k| เป็นไปได้น้อยที่สุดโดยที่ i !=j.
ตัวอย่าง
ถ้า arr[ ] ={0, 4, 6, 2, 4} และ k =7 เราสามารถสร้างคู่ต่อไปนี้ได้ 5 คู่โดยมีค่าน้อยที่สุดเป็น 1
{0, 6}, {4, 2}, {4, 4}, {6, 2}, {2, 4}
อัลกอริทึม
วนซ้ำทุกคู่ที่เป็นไปได้และสำหรับแต่ละคู่เราจะตรวจสอบว่าค่าของ (ai + aj – K) น้อยกว่าค่าที่น้อยที่สุดในปัจจุบันของเราหรือไม่ ตามผลของเงื่อนไขข้างต้น เรามีทั้งหมดสามกรณี −
- abs( ai + aj – K)> เล็กที่สุด − ไม่ทำอะไรเลย เพราะคู่นี้จะไม่นับค่าที่น้อยที่สุดที่เป็นไปได้
- abs(ai + aj – K) =เล็กที่สุด − เพิ่มจำนวนคู่ให้มีค่าน้อยที่สุด
- abs( ai + aj – K) <เล็กที่สุด − อัปเดตค่าที่น้อยที่สุดและตั้งค่าเป็น 1
ตัวอย่าง
#include <iostream>
#include <climits>
#include <cmath>
using namespace std;
void getPairs(int *arr, int n, int k) {
int minValue = INT_MAX;
int pairs = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int val = abs(arr[i] + arr[j] - k); if (val < minValue) {
minValue = val;
pairs = 1;
} else if (val == minValue) {
++pairs;
}
}
}
cout << "Min value = " << minValue << endl; cout << "Total pairs = " << pairs << endl;
}
int main() {
int arr[] = {0, 4, 6, 2, 4};
int k = 7;
int n = sizeof(arr) / sizeof(arr[0]);
getPairs(arr, n, k);
return 0;
} ผลลัพธ์
เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
Min value= 1 Total pairs = 5
