此题我使用的是模拟退火算法
模拟退火虽然是算法,但是大多数时候都用来骗分了
模拟退火解决的一般是最优解问题,如果遇到不会做的最优解的问题
就用模拟退火骗骗分吧!!!
你看,这可是省选题哦,可以骗分的哦


下面我们来介绍一下模拟退火吧
模拟退火简介
好了,我们介绍完了(我觉得上面那篇文章还挺好的)

实现

在我讲实现之前,大家可以先实现一下(你看不见下面
如果这道题就是模拟退火模板题,我会专门写个博客嘛!


我先来解释一下思路
我们考虑一个长度为n的序列
我们挨个分配到m个组内
从心底突然冒出个想法!将我每次将数分配到总和最小的组不就行了嘛()!
可惜我们用手指头想一想都可以hack自己
那我随机一下序列不就行了嘛!!!
哦吼吼吼吼吼吼吼吼吼吼吼吼


但是我先浇你一盆冷水,你的想法是不严谨的
如果要这么做,我们要保证
每种可能为最优解的分组都对应一个或多个随机序列
什么是可能的最优解的分组呢,看下图
图片说明
长度代表数字的大小,这明显不是可能的最优解,因为橙色的线移动到最上面才可能是最优解
可以看出,我们贪心求出的分组一定是可能的最优解
那么考虑一个可能的最优解,若一个分组的一个组去掉最后一个数后,成为所有组中最小的组
那么序列的后面就应该是这个数(即贪心的逆过程)
所以可以证明:每种可能为最优解的分组都对应一个或多个随机序列
还需要证明序列和答案具有连续性,即序列变化越大,答案变化越大,反之亦然
我们才能用随机序列来求解此题
接下来就是模拟退火板子了

参考程序

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[105],p[105];
double sum;
double ans=10101010;
double calc()
{
    memset(p,0,sizeof(p));
    p[0]=1010101;
    for(int i=1;i<=n;i++){
        int k=0;
        for(int j=1;j<=m;j++)
            if(p[k]>p[j]) k=j;
        p[k]+=a[i];
    }
    double res=0;
    for(int i=1;i<=m;i++) res+=(p[i]-sum)*(p[i]-sum);
    return sqrt(res/m);
}
void SA()
{
    for(double T=1010100;T>0.001;T*=0.99){
        int x=rand()%n+1,y=rand()%n+1;
        swap(a[x],a[y]);
        double k=calc()-ans;
        if(k<0)    ans+=k;
        else if(exp(-k/T) > (double)rand()/RAND_MAX )
            swap(a[x],a[y]);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    sum/=m;
    while((double)clock()/CLOCKS_PER_SEC<0.8) SA();
    printf("%.2lf",ans);
    return 0;
}

此题比较简单,建议大家做完后可以去尝试四川省选题: [SCOI2008]城堡