题目大意：把$n(n\leqslant30)$个数分成两组，两组个数最多相差$1$，求出两组元素差的绝对值最小使多少
题解：模拟退火
卡点：$\exp$中的两个数相减写反，导致$\exp(x)$中的$x>0$，$\exp(x)>1$，相当于一直接受生成的解
C++ Code：
#include <algorithm>
#include <cstdio>
#include <cmath>
#define maxn 32
inline long long abs(long long a) {return a > 0 ? a : -a;}
int T, n, divn;
long long sum; const double ST = 100, delT = 0.9992, eps = 1e-5;
int Tim = 20;
struct node {
int s[maxn];
long long w;
} ans;
inline long long calc(node &x) {
long long __sum = 0;
for (int i = 0; i < divn; i++) __sum += x.s[i];
x.w = abs(sum - __sum - __sum);
if (n & 1) x.w = std::min(x.w, abs(sum - __sum - __sum - x.s[divn] - x.s[divn]));
return x.w;
}
inline double rand_d() {return static_cast<double> (rand()) / RAND_MAX;} void SA() {
double T = ST;
node now = ans, nxt;
while (T > eps) {
nxt = now;
int x = rand() % n, y = rand() % n;
T *= delT;
if (x == y) continue;
std::iter_swap(nxt.s + x, nxt.s + y);
long long del = calc(nxt);
if (del < now.w || exp((now.w - del) / T) > rand_d()) now = nxt;
if (del < ans.w) ans = nxt;
}
}
int main() {
srand(20040826);
scanf("%d", &T);
while (T --> 0) {
scanf("%d", &n); divn = n >> 1;
sum = 0;
for (int i = 0; i < n; i++) scanf("%d", ans.s + i), sum += ans.s[i];
if (n == 1) {
printf("%d\n", *ans.s);
continue;
}
std::random_shuffle(ans.s, ans.s + n);
calc(ans);
for (int i = 0; i < Tim; i++) SA();
printf("%lld\n", ans.w);
}
return 0;
}