1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| #include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 40;
int n, w[N];
LL ans;
double rd(double l, double r)
{
return (double)rand() / RAND_MAX * (r - l) + l;
}
int rd(int l, int r)
{
return rand() % (r - l + 1) + l;
}
int cal(vector<int> *v)
{
LL res = 0;
for (int i : v[0])
res += i;
for (int i : v[1])
res -= i;
res = abs(res);
ans = min(ans, res);
return res;
}
void SimulateAnneal()
{
int cnt[2];
vector<int> cur[2];
cnt[0] = n >> 1, cnt[1] = n - cnt[0];
for (int i = 1; i <= n; i++)
{
int t;
if (cur[0].size() == cnt[0] && cur[1].size() < cnt[1])
t = 1;
else if (cur[1].size() == cnt[1] && cur[0].size() < cnt[0])
t = 0;
else
t = rd(0, 1);
cur[t].push_back(w[i]);
}
for (double t = 1e4; t > 1e-2; t *= 0.996)
{
int x = rd(0, cnt[0] - 1), y = rd(0, cnt[1] - 1);
LL k = cal(cur);
swap(cur[0][x], cur[1][y]);
LL delta = cal(cur) - k;
if (exp(-delta / t) <= rd(0.0, 1.0))
swap(cur[0][x], cur[1][y]);
}
}
int main()
{
srand(time(NULL));
int T;
scanf("%d", &T);
for (int t = 1; t <= T; t++)
{
ans = 1e12;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &w[i]);
if (n == 1)
{
printf("%d\n", w[1]);
continue;
}
while ((double)clock() / CLOCKS_PER_SEC < (0.9 / T) * t)
SimulateAnneal();
printf("%lld\n", ans);
}
return 0;
}
|