โปรแกรม C++ เพื่อค้นหาค่าความแตกต่างขั้นต่ำในคู่จำนวนเต็ม n คู่

สมมติว่าเราได้รับอาร์เรย์ a และ b สองอาร์เรย์ที่มีค่ารวม n และ m ตามลำดับ เราต้องทำจำนวนคู่ n หรือ m (แล้วแต่จำนวนใดจะน้อยที่สุด) โดยใช้ค่าจากอาร์เรย์ทั้งสอง คู่ต้องมีค่าจากอาร์เรย์ a และอีกค่าหนึ่งจากอาร์เรย์ b เราจะต้องสร้างคู่ในลักษณะที่ความแตกต่างของมูลค่าในคู่มีค่าน้อยที่สุดและเท่ากัน เราพิมพ์ค่าเป็นผลลัพธ์

ดังนั้น หากอินพุตเป็น n =4, m =4, a ={2, 3, 4, 7}, b ={3, 4, 6, 5} ผลลัพธ์จะเป็น 1

คู่ที่สามารถทำได้คือ −

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

ส่วนต่างของมูลค่าทุกคู่คือ 1.

ขั้นตอน

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

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)

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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;
}

อินพุต

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

ผลลัพธ์

1