P3878 [TJOI2010] 分金币

题意

有 \(n\) 枚金币，第 \(i\) 枚价值为 \(s_i\)。

分成两部分，使得两部分数量之差不超过 \(1\)，求价值之差最小是多少。

Sol

模拟退火！

其实这个算法没什么好说的。

设当前最优解与当前解的差为 \(\Delta E\)。

那么当前状态发生转移的概率为 \(P(f(n)) = \begin{cases} 1, & \text{f' is better than f} \cr e ^ {\frac{\Delta E}{T}}, & \text{Otherwise}\end{cases}\)

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <ctime>
#include <random>
using namespace std;
#ifdef ONLINE_JUDGE

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;

#endif
int read() {
	int p = 0, flg = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') flg = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		p = p * 10 + c - '0';
		c = getchar();
	}
	return p * flg;
}
void write(int x) {
	if (x < 0) {
		x = -x;
		putchar('-');
	}
	if (x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}
bool _stmer;

const int N = 35, inf = 1e9;

array <int, N> s;

int rci(int n) {
	int tp1 = 0, tp2 = 0;
	for (int i = 1; i <= (n + 1) / 2; i++) tp1 += s[i];
	for (int i = (n + 1) / 2 + 1; i <= n; i++) tp2 += s[i];
	return abs(tp1 - tp2);
}

void SA(int& ans, int n) {
	mt19937 rnd(time(0));
	double T = 1e4;
	while (T > 1e-9) {
		int x = rnd() % n + 1, y = rnd() % n + 1;
		swap(s[x], s[y]);
		int _ans = rci(n);
		if (_ans < ans) ans = _ans;
		else if (exp((ans - _ans) / T) * inf < rnd()) swap(s[x], s[y]);
		T *= 0.9147;
	}
}

void solve() {
	int n = read();
	for (int i = 1; i <= n; i++)
		s[i] = read();
	int ans = inf, T = 5000;
	while (T--) SA(ans, n);
	write(ans), puts("");
}

bool _edmer;
int main() {
	cerr << (&_stmer - &_edmer) / 1024.0 / 1024.0 << "MB\n";
	int T = read();
	while (T--) solve();
	return 0;
}