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