题目大意
将$n$个数分成两半，使得这两半的差尽量小
Solution
我们首先先把这$n$个数按下标顺序分成两组，然后每次随机选取前半段和后半段的两个数将其交换，如果更优的话就更新$ans$,否则就以$e^{\frac{-de}{t}}$（$de=$当前解-最优解）的概率接受该交换(其实就是模拟退火的基本套路)
代码
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
| #include <bits/stdc++.h>
#define ll long long
const int MaxN = 50;
const double delta = 0.993;
ll n, a[MaxN], ans;
ll abs(ll x){ return (x > 0) ? x : (-x);}
inline ll calc()
{
ll sum1 = 0, sum2 = 0;
for (int i = 1; i <= n; i++)
{
if(i <= (n + 1) / 2)
sum1 += a[i];
else sum2 += a[i];
}
return abs(sum1 - sum2);
}
inline void sa()
{
double t = 10000000;
while (t > 1e-14)
{
int x = rand() % ((n + 1) / 2) + 1, y = rand() % ((n + 1) / 2) + ((n + 1) / 2);
std::swap(a[x], a[y]);
int now = calc();
int de = now - ans;
if (de < 0)
ans = now;
else if (exp(-de / t) * RAND_MAX <= rand())
std::swap(a[x], a[y]);
t *= delta;
}
}
int main()
{
int T;
srand(time(NULL));
scanf("%d", &T);
while (T--)
{
scanf("%lld", &n);
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
ans = 1e9;
for (int i = 1; i <= 50; i++)
sa();
printf("%lld\n", ans);
}
return 0;
}
|