官方题解｜最小化两数组的距离

题目解析

对于只交换 $1$ 对二元组的情况，我们直接枚举 $A$ 中要交换的二元组和 $B$ 中要交换的二元组即可，时间复杂度 $\mathrm{O}(N^2)$。

我们主要考虑交换 $2$ 对二元组的情况。

首先考虑 $\tt{S}$，在未交换交换元素时，令：

$$\tt{diffS = \sum_i^NAx_i - \sum_i^NBx_i}$$

此时若交换的 $1$ 对二元组分别为 $A_i$ 和 $B_j$，那么：

$$\tt{S = \vert diffS - 2 \times (Ax_i - Bx_j) \vert}$$

对于交换 $2$ 对二元组的情况，我们只需要将 $A$ 中的元素两两结合，$B$ 中的元素两两结合，就可以把选择 $2$ 对二元组交换转化为选择 $1$ 对两两结合后的二元组交换。

那么对于上式，我们可以枚举 $\tt{Ax_i}$，二分 $\tt{Bx_j}$。

具体的，我们把 $B$ 的两两结合的 $\tt{Bx_j}$ 排序去重，然后找到最大的 $\tt{Bx_j}$ 使得 $\tt{diffS - 2 \times (Ax_i - Bx_j) \lt 0}$，此时 $\tt{Bx_j}$ 和 $\tt{Bx_{j + 1}}$ 即为与 $\tt{Ax_i}$ 交换后能够使得 $\tt{S}$ 最小的两个元素，其中 $\tt{Bx_j}$ 或 $\tt{Bx_{j + 1}}$ 可能有一个不存在，要注意判别。

对于 $\tt{T}$ 同理。

整个算法时间复杂度 $\mathrm{O}(N^2\log{N^2})$。

AC 代码

#include <bits/stdc++.h>

using pair = std::pair<int, int>;

constexpr int N = 1000;

int main() {
    int n; std::cin >> n;
    std::vector<int> x1(n), y1(n), x2(n), y2(n);
    for (int i = 0; i < n; ++i)
        std::cin >> x1[i] >> y1[i];
    for (int i = 0; i < n; ++i)
        std::cin >> x2[i] >> y2[i];
	int diffS = 0, diffT = 0;
    for (int i = 0; i < n; ++i) {
        diffS += x1[i] - x2[i];
        diffT += y1[i] - y2[i];
    }
    int s = std::abs(diffS), t = std::abs(diffT);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) {
            int ns = std::abs(diffS - 2 * (x1[i] - x2[j]));
            int nt = std::abs(diffT - 2 * (y1[i] - y2[j]));
            std::tie(s, t) = std::min(pair{s, t}, pair{ns, nt});
        }
    std::vector<int> stX, stY[N + 1];
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j) {
            int x = x2[i] + x2[j], y = y2[i] + y2[j];
            stX.push_back(x);
            stY[x].push_back(y);
        }
    std::sort(stX.begin(), stX.end());
    stX.erase(std::unique(stX.begin(), stX.end()), stX.end());
    for (auto &a : stY) {
        std::sort(a.begin(), a.end());
        a.erase(std::unique(a.begin(), a.end()), a.end());
    }
    auto nearest = [&](std::vector<int> &a, int t) {
        int p = -1;
        for (int i = 1 << 10; i > 0; i >>= 1)
            if (p + i < a.size() and t + a[p + i] * 2 < 0) p += i;
        std::vector<int> res;
        if (p >= 0) res.push_back(a[p]);
        if (p + 1 < a.size()) res.push_back(a[p + 1]);
        return res;
    };
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j) {
            int sx1 = x1[i] + x1[j], sy1 = y1[i] + y1[j];
            for (auto &sx2 : nearest(stX, diffS - 2 * sx1))
                for (auto &sy2 : nearest(stY[sx2], diffT - 2 * sy1)) {
                    int ns = std::abs(diffS - 2 * (sx1 - sx2));
                    int nt = std::abs(diffT - 2 * (sy1 - sy2));
                    std::tie(s, t) = std::min(pair{s, t}, pair{ns, nt});     
                }
        }
    std::cout << s << ' ' << t << '\n';
    return 0;
}