竞赛讨论区 > 【每日一题】1月25日题目精讲
头像
王清楚
编辑于 2021-01-27 15:52
+ 关注

【每日一题】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日更新本题题解
欢迎各位大佬来做题写题解,也欢迎大家踊跃在当日讨论贴中提问!

活动奖励:

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

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

.牛币兑换中心

牛客博客开通方式

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

全部评论

(6) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐