【例73.2】 数组的距离

解题思路

两个数组分别升序排序，双指针比较当前差并更新最小值；较小值所在指针前进，寻找更接近另一值的候选。相等时最小距离0可立即结束。

正确性说明

当a[i]<b[j]时，a[i]与后续更大b的差不会比当前小，可安全丢弃a[i]；另一情况对称。被丢弃元素的最好可能配对都已考虑，因此不漏最小距离。

易错点

两个值必须各来自一个数组；用long long求差。

复杂度

时间O(n log n+m log m)，空间O(n+m)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<long long> a(n), b(m);
    for (auto &x : a)
        cin >> x;
    for (auto &x : b)
        cin >> x;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    int i = 0, j = 0;
    long long ans = LLONG_MAX;
    while (i < n && j < m) {
        ans = min(ans, llabs(a[i] - b[j]));
        if (a[i] < b[j])
            i++;
        else if (a[i] > b[j])
            j++;
        else
            break;
    }
    cout << ans << "\n";
    return 0;
}