T0835 线段匹配

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

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tp;
    cin >> tp;
    while (tp--) {
        int n;
        cin >> n;

        // H = 二倍的半长（= 线段长度），C = 二倍的中心（= l + r）
        vector<ll> H(n), C(n);
        for (int i = 0; i < n; i++) {
            ll l, r;
            cin >> l >> r;
            H[i] = r - l;
            C[i] = l + r;
        }

        // 两条线段配对的贡献 = (H_i + H_j + |C_i - C_j|) / 2
        // 要最大化配对贡献之和，等价于把中心两两配开（最小配最大）
        vector<int> ord(n);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int i, int j) { return C[i] < C[j]; });

        vector<ll> sc(n + 1, 0);   // 排好序的中心前缀和
        ll sumH = 0;
        for (int i = 0; i < n; i++) {
            sc[i + 1] = sc[i] + C[ord[i]];
            sumH += H[ord[i]];
        }

        ll best = 0;
        if (n % 2 == 0) {
            int m = n / 2;
            // 最大 m 个中心之和 - 最小 m 个中心之和
            ll match = (sc[n] - sc[m]) - sc[m];
            best = (sumH + match) / 2;
        } else {
            int m = (n - 1) / 2;
            // 枚举哪个线段最后落单
            for (int k = 0; k < n; k++) {
                ll match;
                if (k <= m) {
                    ll small = sc[m + 1] - C[ord[k]];
                    ll big = sc[n] - sc[m + 1];
                    match = big - small;
                } else {
                    ll small = sc[m];
                    ll big = sc[n] - sc[m] - C[ord[k]];
                    match = big - small;
                }
                ll cand = (sumH + H[ord[k]] + match) / 2;
                best = max(best, cand);
            }
        }

        cout << best << "\n";
    }
    return 0;
}