题目链接

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+10;
const double dt=0.9986;
int t,n,val,a[maxn],nw[maxn],ans[maxn];
inline int calc(int b[])
{
    int res=0,sum1=0,sum2=0;
    for(int i=1;i<=n/2;i++) sum1+=b[i];
    for(int i=n/2+1;i<=n;i++) sum2+=b[i];
    return abs(sum1-sum2);
}
void init()
{
    cin>>n; 
    for(int i=1;i<=n;i++) cin>>a[i],ans[i]=a[i];
    val=calc(ans);
}
inline void SA()
{
    double T=1e9;
    while(T>1e-15)
    {
        int x=rand()%(n/2)+1;
        int y=rand()%(n-n/2)+n/2+1;
        // int x=rand()%n;
        // int y=rand()%n;
        for(int i=1;i<=n;i++) nw[i]=a[i];
        swap(nw[x],nw[y]);
        int e=calc(nw);
        int de=e-val;
        if(de<0)
        {
            val=e;
            swap(a[x],a[y]);
        }
        else if(exp(-de/T)*RAND_MAX>rand()) swap(a[x],a[y]);
        T*=dt;
    }
}
signed main()
{
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    srand(time(0));
    cin>>t;
    while(t--)
    {
        init();
        if(n<=2) 
        {
            cout<<abs(a[1]-a[2])<<endl;
            continue;
        }
        SA();SA();SA();SA();
        printf("%lld\n",val);
    }
    return 0;
}