题解 P3878 【[TJOI2010]分金币】

~~模拟退火杀人事件~~ 本题使用超级骗分大法（模拟退火）~~想不出正解啊~~ 没有学过模拟退火的右转[吊打XXX](https://www.luogu.org/problemnew/show/P1337) 每次随机选2个组别不同的数，交换它们的组别 看代码吧 ```cpp #include <bits/stdc++.h> using namespace std; int n,v[35],sum1,sum2,grp[3][35],ans,len1,len2;//grp[i][j]:第i组的第j个数 const double D = 0.99551748,E = 1e-8; inline int calc() //计算答案 { return abs(sum1 - sum2); } inline void swap_grp(int g1,int g2) //交换组别 { sum1 -= grp[1][g1];sum2 += grp[1][g1]; sum2 -= grp[2][g2];sum1 += grp[2][g2]; swap(grp[1][g1],grp[2][g2]); } void SA() { double T = 3000; int cur_ans = ans; while (T > E) { int x = rand() % len1 + 1,y = rand() % len2 + 1;//随机获取位置 swap_grp(x,y);int nans = calc(),diff = nans - cur_ans; if (diff < 0) { cur_ans = nans;if (ans > cur_ans) ans = cur_ans; } else if (exp(-diff / T) * RAND_MAX > rand()) //接受更差的新的解 cur_ans = nans; else swap_grp(x,y); T *= D;//降温 } } int main () { srand(time(0)); int T; scanf("%d",&T); while (T--) { scanf("%d",&n); sum1 = sum2 = 0;//sum:组内的数的和 len1 = n / 2;len2 = n - len1;//len:分组的长度 for (int i = 1;i <= n;i++) { scanf("%d",&v[i]);//默认前半部分分一组，后一半分一组 if (i <= len1) {grp[1][i] = v[i];sum1 += v[i];} else {grp[2][i - len1] = v[i];sum2 += v[i];} } ans = calc(); if (n == 1) //此处要特判，不然len1会为0 取模时会报RE 我被坑了11次 { printf("%d\n",ans);continue; } for (int i = 1;i <= 15;i++) SA(); printf("%d\n",ans); } return 0; } ```