均分数据

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

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

实现

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

我先来解释一下思路
我们考虑一个长度为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]城堡