思路

题目给出 $2n$ 个数，要求补一个数构成长度为 $2n+1$ 的序列 $a$，满足交替和条件，并且输入的数恰好是 $a$ 删掉一个元素后的多重集。

把交替和条件移项，把 $a_2$ 留在左边：

$$a_2=a_1+(a_3-a_4)+(a_5-a_6)+\dots+(a_{2n-1}-a_{2n})+a_{2n+1}.$$

构造： 把输入的 $2n$ 个数降序排序，最大者作为 $a_1$，其余依次填入 $a_3,a_4,\dots,a_{2n+1}$（于是 $a_3>a_4>\dots>a_{2n+1}$，最后一个是所有输入中的最小值）。令 $a_2$ 等于上式右边的值，即代码中按

$$a_2=a_1+a_3-a_4+a_5-a_6+\dots-a_{2n}+a_{2n+1}$$

累加得到。

正确性：

• 把式子移项回去，正是题目要求的交替和 $a_1=a_2-a_3+a_4-\dots+a_{2n}-a_{2n+1}$；
• $a_2>a_1$：右边除 $a_1$ 外还含正项 $a_{2n+1}\ge1$（$n\ge2$ 时中间各项 $a_{2i-1}-a_{2i}\ge0$ 也非负），所以 $a_2$ 比输入中的所有数都大，与它们互不相同，恰好充当被删去的那个数；
• 值域：$a_1\le10^9$，每个 $a_{2i-1}-a_{2i}\le10^9$（共 $n-1$ 项），再加 $a_{2n+1}\le10^9$，故 $a_2\le(n+1)\cdot10^9\le2\times10^{14}<10^{18}$，long long 足够。

因此输入的 $b$ 恰好是序列 $a$ 删去 $a_2$ 后的多重集，输出合法。

复杂度： 每个测试用例排序主导，时间 $O(n\log n)$，总共 $O(\sum n\log n)$；空间 $O(n)$。

代码

#include<bits/stdc++.h>
#define int long long
#define dd double
#define str string
#define el cout << endl
#define re return
#define ff first
#define ss second
#define pll pair<int,int>
#define pdd pair<dd,dd>
#define all(x) x.begin(),x.end()
#define pb(x) push_back(x)
#define sz(x) (int) x.size()
using namespace std;

void go(){
    int n;cin>>n;
    vector<int>arr(n*2,0),ans(n*2+1,0);   // arr 为输入的 2n 个数，ans 为构造结果
    set<int>ex;                           // 记录输入中出现过的数（本题构造中未再使用）
    for(int i=0;i<n*2;i++){
        cin>>arr[i];
        ex.insert(arr[i]);
    }
    sort(all(arr),greater<int>());        // 从大到小排序

    ans[0] = arr[0];                      // a1 取最大值
    for(int i=1;i<n*2;i++){
        ans[i+1] = arr[i];                // 其余数依次填入 a3, a4, ..., a(2n+1)
    }
    // 计算 a2 = a1 + (a3-a4) + (a5-a6) + ... + a(2n+1)
    int t = arr[0]+arr[1];
    for(int i=2;i<n*2;i+=2){
        t -= arr[i]-arr[i+1];
    }
    ans[1] = t;

    for(int i=0;i<n*2+1;i++){
        cout<<ans[i]<<' ';
    }
    cout<<endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t=1;
    cin >>t;                         // 多组测试数据
    while(t--){
        go();
    }
    return 0;
}