bzoj2428 [HAOI2006]均分数据模拟退火

2021-10-18 22:44:45

[HAOI2006]均分数据

Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 3434 Solved: 1091
[Submit][Status][Discuss]

Description

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

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

Input

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

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

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

Output

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

Sample Input

6 3
1 2 3 4 5 6

Sample Output

0.00

HINT

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

Source

Day2

[Submit][Status][Discuss]

HOME Back

以前也没怎么写过模拟退火，这道题让我知道了一些怎么写

退了10000次火，模拟退火主要靠感觉的吧，

写法也是相当奇怪的

当温度很高的时候，将随机出来的一个数，放入当前组里最小的一组，

当温度比较低的时候，就随机放在一组里，然后判断交换后答案是否更优，是的话就交换，不然随机交换。

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #include<iostream>

 #include<cmath>

 #define N 10007

 #define ll long long

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}

     while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }

 int n,m;

 int sum[N],a[N],belong[N];

 double minans=1e30,ave;

 void SA()

 {

     memset(sum,,sizeof(sum));

     for (int i=;i<=n;i++)

     {

         belong[i]=rand()%m+;

         sum[belong[i]]+=a[i];

     }

     double ans=;

     for (int i=;i<=m;i++)

         ans+=(sum[i]-ave)*(sum[i]-ave);

     double T=;

     while(T>0.1)

     {

         T*=0.9;

         int t=rand()%n+,x=belong[t],y;

         if (T>) y=min_element(sum+,sum+m+)-sum;

         else y=rand()%m+;

         if (x==y) continue;

         double tmp=ans;

         ans-=(sum[x]-ave)*(sum[x]-ave);

         ans-=(sum[y]-ave)*(sum[y]-ave);

         sum[x]-=a[t],sum[y]+=a[t];

         ans+=(sum[x]-ave)*(sum[x]-ave);

         ans+=(sum[y]-ave)*(sum[y]-ave);

         if (ans<=tmp) belong[t]=y;

         else if (rand()%>T) sum[x]+=a[t],sum[y]-=a[t],ans=tmp;

         else belong[t]=y;

     }

     if (ans<minans) minans=ans;

 }

 int main()

 {

     srand();

     n=read(),m=read();

     for (int i=;i<=n;i++)

         a[i]=read(),ave+=a[i];

     ave/=(double)m;

     for (int i=;i<=;i++) SA();

     printf("%.2lf\n",sqrt(minans/m));

 }

码农公寓