此题我使用的是模拟退火算法
模拟退火虽然是算法,但是大多数时候都用来骗分了
模拟退火解决的一般是最优解问题,如果遇到不会做的最优解的问题
就用模拟退火骗骗分吧!!!
你看,这可是省选题哦,可以骗分的哦
下面我们来介绍一下模拟退火吧
模拟退火简介
好了,我们介绍完了(我觉得上面那篇文章还挺好的)
实现
在我讲实现之前,大家可以先实现一下(你看不见下面)
如果这道题就是模拟退火模板题,我会专门写个博客嘛!
我先来解释一下思路
我们考虑一个长度为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]城堡