Sắp tăng dần hai dãy ~a~ và ~b~.

Với mỗi ~a_i~, ta cần tìm ~j~ sao cho ~|a_i+b_j|~ là nhỏ nhất.

Ta thấy khi ~i~ tăng thì ~a_i~ tăng nên ~b_j~ giảm và ~j~ sẽ giảm theo. Do đó có thể sử dụng hai con trỏ để duyệt trong ~O(n)~.

Code tham khảo

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;
const int oo = 2e9 + 100;

int n, a[N], b[N];

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) cin >> b[i];
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n);

    int res = oo;
    for(int i = 1, j = n; i <= n; ++i) {
        while(j > 1 && abs(a[i] + b[j]) >= abs(a[i] + b[j - 1])) --j;
        res = min(res, abs(a[i] + b[j]));
    }
    cout << res;

    return 0;
}