T0875 线段匹配2

#include <bits/stdc++.h>
#include <algorithm>
#include <numeric>
#include <queue>
#include <vector>
using namespace std;

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

    int tp;
    cin >> tp;
    while (tp--) {
        int n;
        cin >> n;
        vector<long long> l(n), r(n);
        for (int i = 0; i < n; ++i) cin >> l[i] >> r[i];

        int k = n / 2; // 能配成的对数

        // 最优解中，贡献 r 的线段的 l+r 一定大于贡献 l 的那条
        vector<int> ord(n);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int x, int y) {
            if (l[x] + r[x] != l[y] + r[y]) return l[x] + r[x] > l[y] + r[y];
            return x < y;
        });

        // suf[t]：ord[t..n-1] 中最小的 k 个 l 之和
        vector<long long> suf(n + 1, 0);
        {
            priority_queue<long long> heap;
            long long sum = 0;
            for (int t = n - 1; t >= 0; --t) {
                heap.push(l[ord[t]]);
                sum += l[ord[t]];
                if ((int)heap.size() > k) {
                    sum -= heap.top();
                    heap.pop();
                }
                suf[t] = sum;
            }
        }

        // 前缀里最大的 k 个 r 之和，与后缀里最小的 k 个 l 之和相减
        priority_queue<long long, vector<long long>, greater<long long>> heap;
        long long sum = 0, best = 0;
        for (int t = 0; t < n; ++t) {
            heap.push(r[ord[t]]);
            sum += r[ord[t]];
            if ((int)heap.size() > k) {
                sum -= heap.top();
                heap.pop();
            }
            if (t + 1 >= k && n - t - 1 >= k) {
                best = max(best, sum - suf[t + 1]);
            }
        }

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