โปรแกรม C++ หาความต่างน้อยที่สุดในคู่อาร์เรย์จำนวนเต็ม n คู่

คำอธิบายปัญหา

สมมติว่าเรามีอาร์เรย์ a และ b ขนาด n และ m ต้องการจับคู่ n หรือ m คู่ (ค่าที่น้อยกว่า) ใช้ค่าจากทั้งสองอาร์เรย์ คู่ต้องมี 1 ค่าจาก a และ 1 ค่าจาก 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

ขั้นตอนการแก้ปัญหา

เรียงลำดับอาร์เรย์ a
กำหนดอาร์เรย์ s1 เริ่มต้น 0
กำหนดอาร์เรย์ s2 เริ่มต้น 0
สำหรับ i := 1 ถึง n-1 เพิ่มทีละ 2:
    ใส่ค่าสุดท้ายของ s1 + a[i] - a[i-1] ลง s1
สำหรับ i := 2 ถึง n-1 เพิ่มทีละ 2:
    ใส่ค่าสุดท้ายของ s2 + a[i] - a[i-1] ลง s2
ans := infinity
สำหรับค่า w ใน b:
    diff := ตำแหน่งแรกใน a ที่ไม่ น้อยกว่า w - ตัวแรกของ a
    sub := s1[diff/2] + s2.back() - s2[diff/2] + abs(a[diff/2*2] - w)
    ans := min(ans, sub)
พิมพ์ ans

ตัวอย่างโค้ด C++

#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