https://www.luogu.org/problem/P2503
【题意】
把n个数以分为m组，计算每一组的和，求得到的这m个数的方差。由于分法是任意的，我们要求这些方差中的最小值
【思路】
首先给定一个序列，计算当前状态的最小方差的方法是，按照顺序加入，每次将数加入和最小的一个集合，最后计算方差。
那么改变答案的方法就是改变序列的顺序。这里我用到的是交换其中的两个数，如果答案变小了就更新，否则有一定概率保留，一定概率换回去
【代码】
#include<cmath> #include<ctime> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #define pf(x) ((x)*(x)) using namespace std; typedef double real; const int N=30; real avg,now,best,sum,a[N],num[N],no[N],be[N]; int n,m; inline real deal(){ real fz=0; memset(num,0,sizeof num); for(int i=1,p=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(num[j]<num[p]) p=j; } num[p]+=no[i]; } for(int i=1;i<=m;i++) fz+=pf(num[i]-avg); return sqrt(real(fz)/real(m)); } int main(){ srand(time(0)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%lf",a+i),no[i]=be[i]=a[i],sum+=a[i]; avg=real(sum)/real(m); best=deal(); for(int it=30;it--;){ now=best; for(int i=1;i<=n;i++) no[i]=be[i]; for(real T=1e5;T>=1e-14;T*=0.97){ int x=rand()%n+1,y=rand()%n+1; for(;x==y;y=rand()%n+1); swap(no[x],no[y]); real tmp=deal(),E=tmp-now; if(tmp<best){ best=tmp; for(int j=1;j<=n;j++) be[j]=no[j]; } if(tmp<now||E/T<real(rand())/real(RAND_MAX)) now=tmp; else swap(no[x],no[y]); } } printf("%.2lf",best); return 0; }
模拟退火的思想在于，如果一个移动会使答案变得更优，我们就接受这个移动；否则我们以一定的概率接受这个移动。
听起来很玄学。根据物理的那套理论，我们定义两个东西：
- 温度$(T)$。它随着时间推移而逐渐降低。
- 增量$(E)$。它描述一次移动获得的好处。从$x$移动到$x‘$的增量定义为$f(x‘)-f(x)$，增量越大，往$x‘$移动的优势越大。
在模拟退火中，如果增量大于$0$，则直接接受这次移动；否则按下面的概率接受移动：
$$P = \exp(\frac{E}{T})$$
听起来十分的玄学。然而它竟然可以得出精度比较好的解。伪代码如下：
T=100.0; //初始温度 for(int i=0;i<100;i++) //控制迭代次数 { tar=getPos(); //在x的周围选一个点 E=f(tar)-f(x); if(E > eps) x=tar; //直接移动 else if(exp(E/T) > random(0,1)) x=tar; //接受移动 T=T*0.99; //降温 }
原文：https://www.cnblogs.com/shenben/p/11332985.html