ข้อความโจทย์
คุณได้รับอาร์เรย์ของ 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) น้อยกว่าค่าที่น้อยที่สุดปัจจุบันหรือไม่ ตามผลลัพธ์ของเงื่อนไขข้างต้น มี 3 กรณี −
- abs(ai + aj – K) > smallest − ไม่ทำอะไร เพราะคู่นี้ไม่นับในค่าน้อยที่สุด
- abs(ai + aj – K) = smallest − เพิ่มจำนวนคู่ที่ให้ค่าน้อยที่สุด
- abs(ai + aj – K) < smallest − อัปเดตค่าน้อยที่สุดและตั้งจำนวนคู่เป็น 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
