题解

本题是一个博弈问题：阿里希望最小化最终价值 $v = \sum |a_i - b_i|$，巴哈明希望最大化 $v$。每一轮阿里选择两个下标 $i,j$，巴哈明可以任意重排 $a_i, a_j, b_i, b_j$ 这四个数。

核心观察

对于任意两个下标 $i$ 和 $j$，设四个数为 $\{a_i, b_i, a_j, b_j\}$。不失一般性，假设排序后为 $x_1 \le x_2 \le x_3 \le x_4$。巴哈明可以将它们重新分配给两个位置。考虑以下三种有代表性的分配方式：

1. 保持不变（或等价形式）：
   分配为 $a_i = x_1, b_i = x_2, a_j = x_3, b_j = x_4$
   贡献为 $(x_2 - x_1) + (x_4 - x_3)$

2. 交换 $b_i$ 和 $a_j$：
   分配为 $a_i = x_1, b_i = x_3, a_j = x_2, b_j = x_4$
   贡献为 $(x_3 - x_1) + (x_4 - x_2)$

3. 交换 $b_i$ 和 $b_j$（或等价形式）：
   分配为 $a_i = x_1, b_i = x_4, a_j = x_2, b_j = x_3$
   贡献为 $(x_4 - x_1) + (x_3 - x_2)$

可以验证，第二种和第三种分配方式得到的价值相同，且比第一种分配方式恰好多出 $2 \times (x_3 - x_2)$。

两种情况

定义区间 $[a_i, b_i]$（若 $a_i > b_i$ 则交换为 $[b_i, a_i]$，因为绝对值只关心差的绝对值，且重排可以交换两者）。
令初始总价值为 $V_0 = \sum |a_i - b_i|$。

情况 1：存在两个区间相交（即存在 $i \neq j$ 使得 $[a_i, b_i] \cap [a_j, b_j] \neq \emptyset$）。
此时阿里可以选择这样一对相交区间对应的下标。对于这一对，四个数排序后必然满足 $x_3$ 和 $x_2$ 来自不同区间，从而巴哈明无法增加这一对的价值（即这一对已经处于上述第二种或第三种分配方式的形态）。阿里只需每次选择同一对相交区间，巴哈明就无法在任何一轮增加总价值。因此答案即为初始价值 $V_0$。

情况 2：所有区间两两不交（任意两个区间要么完全分离，要么一个包含另一个？实际上由于定义 $[a_i,b_i]$ 已排序，若两两不交则它们要么分离要么包含。但若包含，则区间相交，必回到情况 1。因此情况 2 意味着所有区间两两严格分离）。
此时对于任意一对 $i,j$，四个数排序后必然呈现为两个分离区间（例如 $[a_i,b_i]$ 整体小于 $[a_j,b_j]$），即总是处于第一种分配方式的形态。巴哈明可以在阿里选择某对下标后，将这一对变为第二种或第三种分配方式，从而使总价值在 $V_0$ 的基础上增加 $2 \times (x_3 - x_2)$。这里的 $x_3 - x_2$ 恰好是两个区间之间的最近距离（后一区间的左端减去前一区间的右端）。

阿里希望最小化增加量，因此他会选择两个最近的分离区间（即最小化 $x_3 - x_2$）。巴哈明会在阿里选择的那一轮执行一次重排以增加价值，之后阿里仍然只能给出分离区间，但巴哈明在后续轮次中若再次改变会使得某些区间发生相交，进而可能让阿里在后继轮次中迫使价值下降（因为一旦相交，阿里可以转而利用情况 1 阻止巴哈明），因此巴哈明在第一次增加后应停止操作（后续轮次不做改变）。所以最终答案等于：

算法实现

1. 对每个 $i$，令 $l_i = \min(a_i, b_i)$，$r_i = \max(a_i, b_i)$，形成区间 $[l_i, r_i]$。
2. 计算初始价值 $V_0 = \sum (r_i - l_i)$。
3. 将所有区间按左端点 $l_i$ 升序排序。
4. 遍历排序后的区间，检查相邻区间是否相交：
   • 若存在某个相邻区间满足 $l_{i+1} \le r_i$（相交），则属于情况 1，答案为 $V_0$。
   • 若所有相邻区间均不相交（即对所有 $i$ 有 $l_{i+1} > r_i$），则属于情况 2。计算最小间距 $d = \min_i (l_{i+1} - r_i)$，答案为 $V_0 + 2 \times d$。

时间复杂度 $O(n \log n)$，空间复杂度 $O(n)$。

代码参考

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

void solve() {
    int n, k;
    cin >> n >> k;
    vector<ll> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];

    vector<pair<ll, ll>> segs(n);
    ll V0 = 0;
    for (int i = 0; i < n; i++) {
        ll l = min(a[i], b[i]);
        ll r = max(a[i], b[i]);
        segs[i] = {l, r};
        V0 += r - l;
    }

    sort(segs.begin(), segs.end());

    bool intersect = false;
    ll min_gap = LLONG_MAX;
    for (int i = 0; i + 1 < n; i++) {
        if (segs[i + 1].first <= segs[i].second) {
            intersect = true;
            break;
        } else {
            min_gap = min(min_gap, segs[i + 1].first - segs[i].second);
        }
    }

    if (intersect) {
        cout << V0 << "\n";
    } else {
        cout << V0 + 2 * min_gap << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}