正经题解｜最小绝对差值和

题意解析

犹豫只能操作一次，所以我们可以枚举被替换的元素 $A_i$。统计未替换时，$A$ 和 $B$ 的绝对差值和 $\tt{sum}$，然后记录枚举 $A_i$ 的过程中替换后可以减少的差值的最大值 $\tt{maxDiff}$，最后的答案即为 $\tt{sum - maxDiff}$。

接下来我们考虑如果快速求出对于每个 $A_i$ 的 $\tt{diff}$。要想最小化 $A_i - B_i$，那么我们可以在数组 $C$ 中找到一个最接近 $B_i$ 的数字。

使用二分查找在数组 $C$ 中，第一个大于 $B_i$ 的元素下标 $j$，那么此时 $C_{j-1}\ (1 \le j - 1 < N)$ 为最后一个小于等于 $B_i$ 的数字。此时与 $B_i$ 的差最小的元素，为其中一个，取最小值即可。

AC 代码

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

using i64 = long long;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        int n; cin >> n;
        vector<int> a(n), b(n), c(n);
        for (auto &x : a) cin >> x;
        for (auto &x : b) cin >> x;
        for (auto &x : c) cin >> x;
        sort(begin(c), end(c));
        i64 res = 0, max_diff = 0;
        for (int i = 0; i < n; ++i) {
            int real = abs(a[i] - b[i]), changed = real;
            int hi = upper_bound(begin(c), end(c), b[i]) - begin(c);
            int lo = hi - 1;
            if (hi < n)
                changed = min(changed, abs(c[hi] - b[i]));
            if (lo >= 0)
                changed = min(changed, abs(c[lo] - b[i]));
            max_diff = max(max_diff, real * 1LL - changed);
            res += real;
        }
        cout << res - max_diff << '\n';
    }
    return 0;
}

复杂度分析

对于每个 $A_i$ 使用二分查找数组 $C$ 中最接近 $B_i$ 的数字，时间复杂度为 $\mathrm{O}(\log{N})$，总的时间复杂度为 $\mathrm{O}(N\log{N})$。