题号 NC19961
名称 [HAOI2006]均分数据
来源 [HAOI2006]
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

作者：(́安◞౪◟排‵)

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

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

实现

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

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

1月25日更新本题题解
欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目1月30日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴