RT，样例都过不去

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<time.h>
#include<ctime>
#include<queue>
//#pragma GCC optimize(2) 
#define INF 0x3f3f3f3f
#define int long long
#define MAXN 10001
using namespace std;
int n,a[MAXN],sum[MAXN];
double t=3000,delta=0.92,ans;
double cnt;
int work(){
	//算金币差
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+a[i];
	}
	if(n%2==0){
		return abs((sum[n]-sum[n/2])-sum[n/2]);
	}else{
		int x=abs(sum[n]-sum[n/2]-sum[n/2]);//分成[1,n/2]和[n/2+1,n]两堆
		return x;
	}
	return 0; 
}
void kx(){
	t=3000;
	while(t>1e-14){
		int x=rand()%n+1,y=rand()%n+1;//随机交换位置
		if(x==y) continue;
		swap(a[x],a[y]);
		double now=work();//新解
		double Delta=now-ans;//新解与最优解得差
		if(Delta<0){//新解更优
			ans=now;
		}else if(exp(-Delta/t)*RAND_MAX<rand()){//新解更劣，且不满足一定概率接受
			swap(a[x],a[y]);
		}
		t=t*delta;//降温
	}
}
void SA(){
	ans=work();
	double MAX_TIME=0.9;
	while((double)clock()/CLOCKS_PER_SEC<MAX_TIME){//不超时就一直跑
		kx();
	}
}
int T;
signed main(){
	ios::sync_with_stdio(false);
	srand(114514);
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		if(n==1){
			cout<<a[n]<<"\n";
			continue;
		}//特判n=1的情况
		SA();
		cout<<(int)ans<<"\n";
	}
	return 0;
}