仅 AC 前 3 个测试点。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<random>
#define N (1005)
#define M (1005)
#define ll long long
#define INF (0x3f3f3f3f)
#define mod (998244353)
#define PII pair<int,int>
#define ls(xxx) (xxx)<<1
#define rs(xxx) (xxx)<<1|1
using namespace std;
const double eps=1e-10;
const double down=0.91;
int t,n;
ll ans;
ll v[N];
ll myabs(ll x){
	return x<0 ? -x : x;
}
ll calc(){
	ll suml=0,sumr=0;
	for(int i=1;i<=n/2;i++) suml+=v[i];
	for(int i=n/2+1;i<=n;i++) sumr+=v[i];
	return myabs(suml-sumr);
}
//int get_rand(int l,int r){
//	return 1LL*l+rand()%(r-l+1);
//}
void sa(){
	double T=5000;
	while(T>eps){
//		int x=get_rand(1,n/2),
//			y=get_rand(n/2+1,n);
		int x=rand()%n+1,y=rand()%n+1;
		swap(v[x],v[y]);
		ll e_ans=calc();
		ll delta=ans-e_ans;
		if(delta>0) ans=e_ans;
		else if(exp(-delta/T)*RAND_MAX<rand()){
			swap(v[x],v[y]);
		}
		T*=down;
	}
}
void solve(int x){
	while(x--) sa();
}
int main(){
	srand(time(0));
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%lld",&v[i]);
		if(n==1){
			printf("%lld\n",v[1]);
			continue;
		}
//		random_shuffle(v+1,v+n+1);
		ans=calc();
		solve(1000);
		printf("%lld\n",ans);
	}
    return 0;
}