0分爬山求调

#include <iostream>
#include <ctime>
#include <random>
#include <cmath>
#include <algorithm>
using namespace std;
long long t;
long long n;
long long a[35] ,sum = 0;
mt19937 myrand(time(NULL));
long long ans = 0;
void sa() {
	random_shuffle(a + 1 ,a + 1 + n);
	long long sum1 = 0 ,sum2 = 0;
	for(long long i = 1; i <= n / 2; i ++) {
		sum1 += a[i];
	}
	for(long long i = n / 2 + 1; i <= n; i ++) {
		sum2 += a[i];
	}
	ans = min(ans ,abs(sum1 - sum2));
	for(double t = 30000; t >= 1e-7; t *= 0.997) {
		long long pos = myrand() % n / 2 + 1;
		long long pos1 = myrand() % (n - n / 2) + n / 2 + 1;
		long long num_pair = sum1 - a[pos] + a[pos1];
		long long num_pair2 = sum2 - a[pos1] + a[pos];
		if(ans > abs(num_pair - num_pair2)) {
			ans = abs(num_pair - num_pair2);
			sum1 = num_pair;
			sum2 = num_pair2;
			swap(a[pos] ,a[pos1]);
		}
	}
//	return ans;
}
int main() {
	cin >> t;
	while(t --) {
		cin >> n;
		for(long long i = 1; i <= n; i ++) {
			cin >> a[i];
		}
		ans = 1e9;
		for(long long i = 1; i <= 100; i ++) {
			sa();
		}
		cout << ans << endl;
		ans = 1e9; 
	}
	return 0;
}