【每日一题】1月25日题目精讲

题号 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日更新本题题解
欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！