疑似发现新算法：模拟上火

#include<bits/stdc++.h>
using namespace std;
const int N=22;
int n,m,a[N],b[N][N],c[N],d[N];
double sum;
int rnd(int l,int r)
{
    return rand()%(r-l+1)+l;
}
double check()
{
    double cnt=0;
    for(int i=1;i<=m;i++)
    {
        cnt+=(sum-d[i])*(sum-d[i]);
    }
    cnt/=m;
    return sqrt(cnt);
}
double SA()
{
    double ans=1e18+10;
    while(true)
    {
        double mn=check();
        for(double t=1e6;t>=1e-6;t*=99)
        {
            int x=rnd(1,m);
            if(c[x]==1)continue;
            int y=rnd(1,c[x]),to=rnd(1,m);
            if(to==x)continue;
            d[to]+=b[x][y];
            d[x]-=b[x][y];
            b[to][++c[to]]=b[x][y];
            b[x][y]=b[x][c[x]];
            b[x][c[x]--]=0;
            double md=check();
            if(md<mn||exp(-(md-mn)/t)>(double)rand()/RAND_MAX)
            {
                mn=md;
            }
            else
            {
                d[to]+=b[to][c[to]];
                d[x]-=b[to][c[to]];
                b[x][++c[x]]=b[to][c[to]];
                b[to][c[to]]=0;
                c[to]--;
            }
            ans=min(ans,mn);
            if((double)clock()/CLOCKS_PER_SEC>=0.95)
            {
                return ans;
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
    {
        int j=(i-1)%m+1;
        b[j][++c[j]]=a[i];
        d[j]+=a[i];
        sum+=a[i];
    }
    sum=sum/m;
    printf("%.2lf\n",SA());
    return 0;
}