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

Cho mảng a (n phần tử) và b (m phần tử). Tạo min(n,m) cặp (mỗi cặp 1 từ a, 1 từ b) sao cho chênh lệch trong mọi cặp đều bằng nhau và nhỏ nhất có thể. In giá trị chênh lệch đó.

Ví dụ

Với n=4,m=4, a={2,3,4,7}, b={3,4,6,5}, đầu ra 1. Cặp: (3,4),(4,5),(7,6),(2,3) chênh lệch đều 1.

Giải thuật

Sắp xếp a. Tính tiền tố s1 (chênh lệch cặp (a1,a2), (a3,a4)...) và s2 (cặp (a2,a3), (a4,a5)...). Với mỗi w trong b, tìm vị trí diff trong a (lower_bound). Chi phí = s1[diff/2] + s2.back() - s2[diff/2] + |a[diff/2*2] - w|. Lấy min.

Mã 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}, 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 / Đầu ra

Input: 4, 4, {2, 3, 4, 7}, {3, 4, 6, 5}
Output: 1