Đề bài
Bạn được cho một mảng n số nguyên và một số nguyên K. Tìm số cặp không có thứ tự {i, j} sao cho giá trị tuyệt đối của |ai + aj - k| là nhỏ nhất có thể, với i != j.
Ví dụ
Nếu arr[] = {0, 4, 6, 2, 4} và k = 7 thì có thể tạo 5 cặp sau với giá trị tối thiểu là 1:
{0, 6}, {4, 2}, {4, 4}, {6, 2}, {2, 4}
Thuật toán
Duyệt qua tất cả các cặp có thể và đối với mỗi cặp, kiểm tra xem giá trị (ai + aj - K) có nhỏ hơn giá trị nhỏ nhất hiện tại hay không. Theo kết quả của điều kiện trên, chúng ta có tổng cộng ba trường hợp:
- abs(ai + aj - K) > nhỏ nhất − không làm gì vì cặp này không tính vào giá trị tối thiểu.
- abs(ai + aj - K) = nhỏ nhất − tăng số cặp cho ra giá trị tối thiểu.
- abs(ai + aj - K) < nhỏ nhất − cập nhật giá trị nhỏ nhất và đặt đếm = 1.
Ví dụ
#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 << "Giá trị nhỏ nhất = " << minValue << endl;
cout << "Tổng cặp = " << 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;
}
Kết quả
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:
Giá trị nhỏ nhất = 1 Tổng cặp = 5