BZOJ2428[HAOI2006]均分数据——模拟退火-白红宇

BZOJ2428[HAOI2006]均分数据——模拟退火

阅读量：5754 次

发布时间：2019-06-18

本文共 1674 字，大约阅读时间需要 5 分钟。

题目描述

已知N个正整数：A1、A2、……、An 。今要将它们分成M组，使得各组数据的数值和最平均，即各组的均方差最小。均方差公式如下：

,其中σ为均方差，是各组数据和的平均值，x_i为第i组数据的数值和。

输入

第一行是两个整数，表示N,M的值（N是整数个数，M是要分成的组数）

第二行有N个整数，表示A1、A2、……、An。整数的范围是1--50。

（同一行的整数间用空格分开）

输出

这一行只包含一个数，表示最小均方差的值(保留小数点后两位数字)。

样例输入

6 3

1 2 3 4 5 6

样例输出

0.00

提示

对于全部的数据，保证有K<=N <= 20，2<=K<=6

模拟退火，每次退火先将每个数随机分组，然后在降温过程中每次将一个数的所属分组改变，当答案更优时则保存改变，但当答案变劣时也有一定几率保存改变。最后将每次退火得到的最优解取最小值即可。

#include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 using namespace std;double a[100];double sum[100];int pos[100];double avr;double tmpans;double ans=0x3fffffff;int n,m;void SA(){ memset(sum,0,sizeof(sum)); for(int i=1;i<=n;i++) { pos[i]=rand()%m+1; sum[pos[i]]+=a[i]; } tmpans=0; for(int i=1;i<=m;i++) { tmpans+=(sum[i]-avr)*(sum[i]-avr); } for(double T=10000;T>0.001;T*=0.98) { int x=rand()%n+1; int block; double tmp=tmpans; if(T>500) { block=min_element(sum+1,sum+1+m)-sum; } else { block=rand()%m+1; } if(pos[x]==block)continue; tmpans-=(sum[pos[x]]-avr)*(sum[pos[x]]-avr); tmpans+=(sum[pos[x]]-a[x]-avr)*(sum[pos[x]]-a[x]-avr); tmpans-=(sum[block]-avr)*(sum[block]-avr); tmpans+=(sum[block]+a[x]-avr)*(sum[block]+a[x]-avr); if(rand()%10000+1>T&&tmpans>tmp) { tmpans=tmp; } else { sum[pos[x]]-=a[x]; sum[block]+=a[x]; pos[x]=block; } } ans=min(ans,tmpans);}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%lf",&a[i]); avr+=a[i]; swap(a[i],a[rand()%i+1]); } avr/=(double)m; for(int i=1;i<=6000;i++) { SA(); } printf("%.2f\n",sqrt(ans/(double)m));}

转载于:https://www.cnblogs.com/Khada-Jhin/p/10456964.html

你可能感兴趣的文章