RT，又调疯了

#include <bits/stdc++.h>

#define int long long
// FOR templates.
#define rep(i, s, n, k) for(int i = s;i <= n;i += k)
#define repn(i, s, n, k) for(int i = s;i < n;i += k)
#define pre(i, s, n, k) for(int i = s;i >= n;i -= k)
#define pren(i, s, n, k) for(int i = s;i > n;i -= k)
// Abbr for STL.
#define pii pair<int, int>
#define pdd pair<double, double>
#define mpi map<int, int>
#define pii pair<int, int>
#define pdd pair<double, double>
#define vc vector<int>
#define mpp map<int, int>
#define arr(k, n) int k[n]
#define all(v) v.begin(), v.end()
// CIN templates, proven very useful.
#define cn(n) int n;cin >> n
#define cm(n) cin >> n
// Abbr for funcs.
#define pb push_back
#define mset memset
// #define files
using namespace std;
const int MAXN = 0x3f3f3f3f3f3f3f3fLL;
const int MOD1 = 1000000007LL;
const int MOD2 = 998244353LL;
int d[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int gcd(int a, int b) {if(b == 0) return a; return gcd(b, a % b);}
inline int lowbit(int x) {return x & (-x);}
inline int lcm(int a, int b) {return a * b / gcd(a, b);}

const double BG = 100000;
const double ED = 1e-12;
const double DT = 0.99999998;

int n, a[101]; vector<int> la, ra;
int ans = INT_MAX;

double randd(){
    return (double)((double)rand() / (double)RAND_MAX);
}
int random(int tmp){
    return (int)(randd() * (double)tmp);
}

int check(vc x, vc y){
    int cnt = 0;
    repn(i, 0, la.size(), 1) cnt += a[x[i]];
    repn(i, 0, ra.size(), 1) cnt -= a[y[i]];
    cnt = abs(cnt);
    if(cnt < ans){
        ans = cnt;
        la = x; ra = y;
    }
    return cnt;
}
void dec_tmp(){
    srand(time(0));
    int tmp = BG; vc x = la, y = ra;
    while(tmp > ED){
        vc nx = x, ny = y;
        int lp = random(tmp) % x.size();
        int rp = random(tmp) % y.size();
        swap(nx[lp], ny[rp]);
        if(randd() < exp(-(double)(check(x, y) - check(nx, ny)) / tmp)){
            x = nx, y = ny;
        }
        tmp *= DT;
    }
    repn(i, 0, 10000, 1){
        vc nx = x, ny = y;
        int lp = random(tmp) % x.size();
        int rp = random(tmp) % y.size();
        swap(nx[lp], ny[rp]);
        check(nx, ny);
    }
}

signed main(){
#ifdef files
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cn(t); while(t--){
        ans = INT_MAX;
        cm(n); repn(i, 0, n, 1) cm(a[i]);
        if(n == 1){
            cout << a[0] << endl;
            continue;
        }
        la.clear(); ra.clear();
        repn(i, 0, n / 2, 1) la.pb(i);
        repn(i, n / 2, n, 1) ra.pb(i);
        dec_tmp();
        cout << ans << endl;
    }
	return 0;
}

/*
 *  things to check
 *  1.  int overflow or long long memory need
 *  2.  recursion/array/binary search/dp/loop bounds
 *  3.  precision
 *  4.  special cases(n=1,bounds)
 *  5.  delete debug statements
 *  6.  initialize(especially multi-tests)
 *  7.  = or == , n or m ,++ or -- , i or j , > or >= , < or <=
 *  8.  keep it simple and stupid
 *  9.  do not delete, use // instead
 *  10. operator priority
 *  11. is there anything extra to output?
 *  12. THINK TWICE CODE ONCE, THINK ONCE DEBUG FOREVER
 *  13. submit ONCE, AC once. submit twice, WA forever
 *  14. calm down and you'll get good rank
 *  15. even a bit wrong scores zero
 *  16. ...
 **/
 
/*
 *  something to think about
 *  1. greedy? dp? searching? dp with matrix/ segment tree? binary search? ...?
 *  2. If it is difficult, why not the opposite?
 **/