题解 P2503 【[HAOI2006]均分数据】

其实用不着dp的，纯模拟退火就可以A掉本题 (调参数让我累死) %你退火步骤： > 每次随机更改一个数的分组，然后计算答案 其他的步骤和普通模拟退火一样（这份代码其实有个bug，但不影响最终出的解） ~~我是非洲大酋长~~ ```cpp #include <bits/stdc++.h> using namespace std; int n,m,a[25],grp[25],sum[25];//a:数字 grp:对应的组的编号 sum：组里数字的和 double ans,avg;//avg:均值 const double d = 0.992; double get_val() //计算答案 { double val = 0; for (int i = 1;i <= m;i++) val += (sum[i] - avg) * (sum[i] - avg); return val / m;//最后开方 } void ch_grp(int pos,int target) //将第pos个数的分组改为target { sum[grp[pos]] -= a[pos]; sum[target] += a[pos]; grp[pos] = target; } void SA() //模拟退火 { double T = 3000,cur_ans = ans; while (T > 1e-10) { int pos = rand() % n + 1,target = rand() % m + 1; int origin = grp[pos]; ch_grp(pos,target); double nans = get_val(),diff = nans - cur_ans; if (diff < 0) { cur_ans = nans;if (cur_ans < ans) ans = cur_ans; } else if (RAND_MAX * exp(-diff / T) <= rand()) ch_grp(pos,origin);//如果取新解失败就换回去 T *= d; } } int main () { srand(time(0)); scanf("%d%d",&n,&m); for (int i = 1;i <= n;i++) { scanf("%d",&a[i]);avg += a[i]; } avg /= m; for (int i = 1;i <= n;i++) { grp[i] = rand() % m + 1;sum[grp[i]] += a[i]; } ans = get_val(); for (int i = 1;i <= 1000;i++) SA(); printf("%.2lf",sqrt(ans)); return 0; } ``` ### 跑1000遍SA也没有TLE。。。 ### 附：bug就是可能会出现一组里没有任何数的情况