思路分析

操作的本质是：对于每个 $i\;(1\le i\le n)$，我们可以独立决定是否交换位置 $i$ 与 $i+n$ 上的骑士。用一个二进制变量 $x_i$ 表示是否交换（$0$ 表示不交换，$1$ 表示交换）。那么最终位置 $p$（$1$-indexed）上的骑士为：

• 若 $p\le n$：当 $x_p=0$ 时为 $a_p$，否则为 $a_{p+n}$；
• 若 $p>n$：当 $x_{p-n}=0$ 时为 $a_p$，否则为 $a_{p-n}$。

每张课桌 $i$ 包含两个连续的位置 $2i-1$ 和 $2i$，它们分别属于不同的“对”（因为 $n\ge2$ 时 $2i-1$ 与 $2i$ 相差 $1$，而同一对的两个位置相差 $n\ge2$）。定义位置 $p$ 所属的对编号为 $(p-1)\bmod n+1$，记为 $f(p)$。那么课桌 $i$ 的两个对编号为： [ u_i = f(2i-1) = ((2i-2)\bmod n)+1,\qquad v_i = f(2i) = ((2i-1)\bmod n)+1. ] 它们满足 $v_i \equiv u_i+1 \pmod n$（模 $n$ 意义下连续）。课桌 $i$ 的总和为： [ S_i = \big(x_{u_i}? a_{u_i+n}:a_{u_i}\big) + \big(x_{v_i}? a_{v_i+n}:a_{v_i}\big). ] 因此每个 $S_i$ 仅依赖于两个相邻的变量 $x_{u_i},x_{v_i}$。

将 $n$ 个变量看作节点，每个课桌看作连接 $u_i$ 与 $v_i$ 的一条无向边，则每个节点恰好连接两条边（因为每个 $x_j$ 会作为 $u_i$ 出现在一个课桌，作为 $v_i$ 出现在另一个课桌）。于是整个图是由若干个环构成的（可能包含两个节点之间有两条平行边的情况）。每个环内部变量相互依赖，不同环之间变量独立。

我们的目标是为每个节点 $x_j\in\{0,1\}$ 赋值，使得所有边的权值 $S_i$ 的最大值与最小值之差最小。

处理单个环

对于一个有 $m$ 个节点和 $m$ 条边的环（节点按顺序 $v_0,v_1,\dots,v_{m-1}$，边 $e_i$ 连接 $v_i$ 与 $v_{i+1}$，下标模 $m$），每条边有四个可能的权值： [ w_i[a][b] = \big(a? a_{v_i+n}:a_{v_i}\big) + \big(b? a_{v_{i+1}+n}:a_{v_{i+1}}\big),\quad a,b\in{0,1}. ] 我们需要选择 $x_{v_0},\dots,x_{v_{m-1}}$ 使得所有 $w_i[x_{v_i}][x_{v_{i+1}}]$ 的最大值与最小值之差最小。

固定最小值求解最大值的最小值

固定一个下界 $L$（即要求所有边权 $\ge L$），定义函数 $f(L)$ = 在满足边权 $\ge L$ 的前提下，环上边权最大值的最小可能值（若不可行则 $f(L)=\infty$）。则答案即为 $\min\limits_{L}\big(f(L)-L\big)$，其中 $L$ 取遍所有可能出现的边权值（因为最优解的最小值一定是某个边权）。

对于固定的 $L$，可以在环上做 DP：

• 枚举 $x_{v_0}=0$ 或 $1$。
• 设 $dp[i][c]$ 表示处理到节点 $v_i$（已确定 $x_{v_i}=c$），且从边 $e_0$ 到 $e_{i-1}$ 的权值最大值的最小可能值。初始化 $dp[0][c]=-\infty$。
• 转移：对于 $i$ 从 $0$ 到 $m-1$，考虑边 $e_i$，已知 $x_{v_i}=a$，枚举 $b\in\{0,1\}$，若 $w_i[a][b]\ge L$，则新最大值 $=\max(dp[i][a],\,w_i[a][b])$，用其更新 $dp[i+1][b]$。
• 处理完所有 $m$ 条边后，需要 $x_{v_m}=x_{v_0}$，因此取 $dp[m][x_{v_0}]$ 作为该起始状态的结果。
• 对两种起始状态取最小值，即为 $f(L)$。

单环的 DP 时间复杂度 $O(m)$。

合并多个环

因为不同环之间变量独立，所以全局的可行性要求每个环均存在赋值使得边权 $\ge L$。此时全局最大值为各环 $f(L)$ 的最大值。于是对于每个候选 $L$，计算： [ \text{全局最大值} = \max_{\text{环 }R} f_R(L),\quad \text{差值} = \text{全局最大值} - L, ] 取所有可行 $L$ 中的最小差值即为答案。

候选 $L$ 只需取所有边权的可能取值（共 $4n$ 个），排序去重后依次检查。总复杂度 $O(n^2)$，因为 $n$ 的总和不超过 $2000$。

特殊处理 $n=1$

当 $n=1$ 时，只有一张课桌，总和恒为 $a_1+a_2$，差值为 $0$，直接输出。

算法步骤

1. 读入 $t$。
2. 对每个测试用例：
   • 若 $n=1$，输出 $0$ 并跳过。
   • 读入数组 $a[0..2n-1]$。
   • 构建图：对每个课桌 $i=0..n-1$： $u = (2i)\bmod n,\; v = (2i+1)\bmod n$。 记录边 $e_i$ 连接节点 $u$ 与 $v$，并存储四个权值： [ \begin{aligned} w[i][0][0] &= a[u] + a[v] \ w[i][0][1] &= a[u] + a[v+n] \ w[i][1][0] &= a[u+n] + a[v] \ w[i][1][1] &= a[u+n] + a[v+n] \end{aligned} ] 同时将边加入邻接表 adj[u].push_back({v,i})，adj[v].push_back({u,i})。
   • 找出所有环（连通分量）： vis 数组标记节点，对每个未访问节点进行 DFS/迭代，沿着度数为 $2$ 的边走，收集节点序列和边序列，得到每个环的有向顺序。
   • 收集所有可能的权值到列表 all_vals 中。
   • 初始化答案 ans = INF。
   • 对 all_vals 排序去重，依次枚举每个值作为 $L$： global_max = 0，可行标志 ok = true。 对每个环，调用 calc_ring(ring, L) 得到该环的最小可能最大值 $f$，若 $f=\infty$ 则 ok=false 并跳出；否则 global_max = max(global_max, f)。 若 ok 为真，则更新 ans = min(ans, global_max - L)。
   • 输出 ans。

复杂度分析

• 建图 $O(n)$。
• 找环 $O(n)$。
• 候选 $L$ 数量 $O(n)$，每个 $L$ 对所有环做 DP，总环大小和为 $O(n)$，故总时间 $O(n^2)$。
• $n$ 总和 $\le 2000$，实际运行很快。

参考代码（C++）

```cpp
#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;

int solve_ring(const vector<array<array<int,2>,2>>& w, int L) {
    int m = w.size();
    if (m == 0) return -INF;
    auto dp = [&](int start) -> int {
        int cur[2] = {INF, INF};
        cur[start] = -INF;
        for (int i = 0; i < m; ++i) {
            int nxt[2] = {INF, INF};
            for (int a = 0; a < 2; ++a) {
                if (cur[a] >= INF) continue;
                for (int b = 0; b < 2; ++b) {
                    int val = w[i][a][b];
                    if (val < L) continue;
                    int cand = max(cur[a], val);
                    if (cand < nxt[b]) nxt[b] = cand;
                }
            }
            cur[0] = nxt[0], cur[1] = nxt[1];
        }
        return cur[start];
    };
    return min(dp(0), dp(1));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(2 * n);
        for (int i = 0; i < 2 * n; ++i) cin >> a[i];
        if (n == 1) {
            cout << "0\n";
            continue;
        }
        vector<int> edge_u(n), edge_v(n);
        vector<array<array<int,2>,2>> edge_w(n);
        vector<vector<pair<int,int>>> adj(n);
        for (int i = 0; i < n; ++i) {
            int u = (2 * i) % n;
            int v = (2 * i + 1) % n;
            edge_u[i] = u, edge_v[i] = v;
            edge_w[i][0][0] = a[u] + a[v];
            edge_w[i][0][1] = a[u] + a[v + n];
            edge_w[i][1][0] = a[u + n] + a[v];
            edge_w[i][1][1] = a[u + n] + a[v + n];
            adj[u].emplace_back(v, i);
            adj[v].emplace_back(u, i);
        }
        vector<bool> vis(n, false);
        vector<vector<array<array<int,2>,2>>> rings;
        for (int s = 0; s < n; ++s) {
            if (vis[s]) continue;
            vector<int> nodes, edges;
            int cur = s, prev = -1;
            while (true) {
                vis[cur] = true;
                nodes.push_back(cur);
                int nxt_node = -1, nxt_edge = -1;
                for (auto &p : adj[cur]) {
                    if (p.second == prev) continue;
                    nxt_node = p.first;
                    nxt_edge = p.second;
                    break;
                }
                edges.push_back(nxt_edge);
                if (nxt_node == s) break;
                cur = nxt_node;
                prev = nxt_edge;
            }
            int m = nodes.size();
            vector<array<array<int,2>,2>> ring_w(m);
            for (int j = 0; j < m; ++j) {
                int u = nodes[j], v = nodes[(j + 1) % m], ei = edges[j];
                if (edge_u[ei] == u && edge_v[ei] == v) {
                    ring_w[j] = edge_w[ei];
                } else {
                    for (int a = 0; a < 2; ++a)
                        for (int b = 0; b < 2; ++b)
                            ring_w[j][a][b] = edge_w[ei][b][a];
                }
            }
            rings.push_back(move(ring_w));
        }
        vector<int> vals;
        for (int i = 0; i < n; ++i)
            for (int a = 0; a < 2; ++a)
                for (int b = 0; b < 2; ++b)
                    vals.push_back(edge_w[i][a][b]);
        sort(vals.begin(), vals.end());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());
        int ans = INF;
        for (int L : vals) {
            int global_max = 0;
            bool ok = true;
            for (auto &ring : rings) {
                int cur = solve_ring(ring, L);
                if (cur >= INF) { ok = false; break; }
                if (cur > global_max) global_max = cur;
            }
            if (ok) ans = min(ans, global_max - L);
        }
        cout << ans << '\n';
    }
    return 0;
}