Chương trình C ++ để tìm ra giá trị chênh lệch nhỏ nhất trong n cặp số nguyên

Giả sử, chúng ta được cho hai mảng a và b có tổng giá trị n và m tương ứng. Chúng ta phải tạo n hoặc m số cặp (tùy theo giá trị nào nhỏ nhất) bằng cách sử dụng các giá trị từ hai mảng. Một cặp phải chứa một giá trị từ mảng a và một giá trị khác từ mảng b. Chúng ta phải tạo các cặp theo cách sao cho sự khác biệt của giá trị trong các cặp là nhỏ nhất và bằng nhau. Chúng tôi in giá trị dưới dạng đầu ra.

Vì vậy, nếu đầu vào là n =4, m =4, a ={2, 3, 4, 7}, b ={3, 4, 6, 5}, thì đầu ra sẽ là 1.

Các cặp có thể được thực hiện là -

(3, 4), (4, 5), (7, 6), (2, 3).

Sự khác biệt về giá trị trong tất cả các cặp là 1.

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

sort the array a
Define an array s1 initialized with 0
Define an array s2 initialized with 0
for initialize i := 1, when i < n, update i := i + 2, do:
   insert last element of s1 + a[i] - a[i - 1] at the end of s1
for initialize i := 2, when i < n, update i := i + 2, do:
   insert last element of s2 + a[i] - a[i - 1] at the end of s2
ans := infinity
for each value w in b, do:
   diff := first element in the array a not less than w - first value of a
   sub := last element of s1[diff / 2] + s2
   ans := minimum of ans and sub
print(ans)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

void solve(int n, int m, vector<int> a, vector<int> b){
   sort(a.begin(), a.end());
   vector<int> s1 = {0};
   vector<int> s2 = {0};
   for (int i = 1; i < n; i += 2)
      s1.push_back(a[i] - a[i - 1] + s1.back());
   for (int i = 2; i < n; i += 2)
      s2.push_back(a[i] - a[i - 1] + s2.back());
   int ans = INF;
   for (const auto & w : b) {
      int diff = lower_bound(a.begin(), a.end(), w) - a.begin();
      int sub = s1[diff / 2] + s2.back() - s2[diff / 2] + abs(a[diff / 2 * 2] - w);
      ans = min(ans, sub);
   }
   cout << ans << endl;
}
int main() {
   int n = 4, m = 4;
   vector<int> a = {2, 3, 4, 7}, b = {3, 4, 6, 5};
   solve(n, m, a, b);
   return 0;
}

Đầu vào

4, 4, {2, 3, 4, 7}, {3, 4, 6, 5}

Đầu ra

1