模拟退火（退役前怒学骗分）

代码是 \([这题](https://www.luogu.com.cn/problem/P3878)\)的。
模拟一个退火的过程，最开始温度为 \(100\) 不断降低，常数可以自己设计这里为 \(99\)。
每次随机一个转移，如果这个转移更优，就直接做，反之做的概率为 \(e^{\Delta f / T}\)，\(T\) 为温度， \(e\) 为自然常数， \(\Delta f\) 表示前后函数差值。

#include<bits/stdc++.h>
#define RG register
#define LL long long
#define U(x, y, z) for(RG int x = y; x <= z; ++x)
#define D(x, y, z) for(RG int x = y; x >= z; --x)
#define update(x, y) (x = x + y >= mod ? x + y - mod : x + y)
using namespace std;
const int mod = 998244353;
namespace FastIO {
#define il inline
const int iL = 1 << 25;
char ibuf[iL], *iS = ibuf + iL, *iT = ibuf + iL;
#define GC() (iS == iT) ? \
  (iT = (iS = ibuf) + fread(ibuf, 1, iL, stdin), (iS == iT) ? EOF : *iS++) : *iS++
void read(){}
template<typename _Tp, typename... _Tps>
void read(_Tp &x, _Tps &...Ar) {
    x = 0; char ch = GC(); bool flg = 0;
    for (; !isdigit(ch); ch = GC()) flg |= (ch == '-');
    for (; isdigit(ch); ch = GC()) x = (x << 1) + (x << 3) + (ch ^ 48);
    if (flg) x = -x;
    read(Ar...);    
}
char Out[iL], *iter = Out;
#define Flush() fwrite(Out, 1, iter - Out, stdout); iter = Out
template <class T>il void write(T x, char LastChar = '\n') {
    int c[35], len = 0;
    if (x < 0) {*iter++ = '-'; x = -x;}
    do {c[++len] = x % 10; x /= 10;} while (x);
    while (len) *iter++ = c[len--] + '0';
    *iter++ = LastChar; Flush();
}
template <typename T> inline void writeln(T n){write(n, '\n');}
template <typename T> inline void writesp(T n){write(n, ' ');}
inline char Getchar(){ char ch; for (ch = GC(); !isalpha(ch); ch = GC()); return ch;}
inline void readstr(string &s) { s = ""; static char c = GC(); while (isspace(c)) c = GC(); while (!isspace(c)) s = s + c, c = GC();}
}
using namespace FastIO;
struct modint{
    int x;
    modint(int o=0){x=o;}
    modint &operator = (int o){return x=o,*this;}
    modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
    modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
    modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
    modint &operator ^=(int b){
        if(b<0)return x=0,*this;
        b%=mod-1;
        modint a=*this,c=1;
        for(;b;b>>=1,a*=a)if(b&1)c*=a;
        return x=c.x,*this;
    }
    modint &operator /=(modint o){return *this *=o^=mod-2;}
    modint &operator +=(int o){return x=x+o>=mod?x+o-mod:x+o,*this;}
    modint &operator -=(int o){return x=x-o<0?x-o+mod:x-o,*this;}
    modint &operator *=(int o){return x=1ll*x*o%mod,*this;}
    modint &operator /=(int o){return *this *= ((modint(o))^=mod-2);}
    template<class I>friend modint operator +(modint a,I b){return a+=b;}
    template<class I>friend modint operator -(modint a,I b){return a-=b;}
    template<class I>friend modint operator *(modint a,I b){return a*=b;}
    template<class I>friend modint operator /(modint a,I b){return a/=b;}
    friend modint operator ^(modint a,int b){return a^=b;}
    friend bool operator ==(modint a,int b){return a.x==b;}
    friend bool operator !=(modint a,int b){return a.x!=b;}
    bool operator ! () {return !x;}
    modint operator - () {return x?mod-x:0;}
};
template <typename T> inline void chkmin(T &x, T y){x = x < y ? x : y;}
template <typename T> inline void chkmax(T &x, T y){x = x > y ? x : y;}
template <typename T> inline T Min(T x, T y){return x < y ? x : y;}
template <typename T> inline T Max(T x, T y){return x > y ? x : y;}
inline void FO(string s){freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout);}

#define db double
const int N = 55, inf = 1e9;
const db D = 0.99, eps = 1e-8;
int n, m, k, ans = inf, res, tot, now, T;
int v[N];

mt19937 rnd(19260817);

inline void init() {
	ans = inf;
	read(n);
	U(i, 1, n) read(v[i]);
}

inline int calc() {
	int s1 = 0, s2 = 0;
	U(i, 1, n / 2) s1 += v[i];
	U(i, n / 2 + 1, n) s2 += v[i];
	return abs(s1 - s2);
}

inline void solve() {
	db T = 100;
	int p1, p2;
	now = calc();
	while (T > eps) {
		p1 = rnd() % n + 1, p2 = rnd() % n + 1;
		if (p1 == p2) continue ;
		swap(v[p1], v[p2]);
		res = calc();
		chkmin(ans, res);
		if (exp(((db) now - res) / (T)) < (db) (rnd() % (inf + 1)) / inf) swap(v[p1], v[p2]);
		else now = res;
		T *= D;
	}
}

int main(){
	//FO("");
	int T;
	read(T);
	while (T--) {
		init();
		if (n == 1) {
			writeln(v[1]);
			continue ;
		}
		U(i, 1, 50) {
			random_shuffle(v + 1, v + n + 1);
			solve();
		}
		writeln(ans);
	}
	return 0;
}