暴力枚举

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int m, n;
int a[MAXN + 5], b[MAXN + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> m >> n;
    for (int i = 1; i <= m; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];

    sort(a + 1, a + m + 1);
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        int now = abs(a[1] - b[i]);
        for (int j = 2; j <= m; j++)
            now = min(now, abs(a[j] - b[i]));
        sum += now;
    }
    cout << sum;

    return 0;
}

二分

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int m, n;
int a[MAXN + 5], b[MAXN + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> m >> n;
    for (int i = 1; i <= m; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];

    sort(a + 1, a + m + 1);
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        // 找到了第一个大于等于 b[i] 的下标
        int pos = lower_bound(a + 1, a + m + 1, b[i]) - a;
        if (pos == 1)
            sum += abs(a[pos] - b[i]);
        else if (pos == m + 1)
            sum += abs(a[pos - 1] - b[i]);
        else
            sum += min(abs(a[pos] - b[i]),
                       abs(a[pos - 1] - b[i]));
    }
    cout << sum;

    return 0;
}

双指针

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int MAXM = 100000;
int n, m;
int a[MAXN + 5];
int b[MAXM + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= m; i++)
        cin >> b[i];
    // work
    sort(a + 1, a + n + 1);
    sort(b + 1, b + m + 1);
    long long ans = 0;
    int pos = 1; // a[pos]>=b[i]
    for (int i = 1; i <= m; i++)
    {
        while (pos <= n && a[pos] < b[i])
            pos++;
        if (pos == 1)
            ans += abs(a[pos] - b[i]);
        else if (pos == n + 1)
            ans += abs(a[n] - b[i]);
        else
            ans += min(abs(a[pos] - b[i]), abs(a[pos - 1] - b[i]));
    }
    cout << ans << "\n";
    return 0;
}