BZOJ2428:[HAOI2006]均分数据(模拟退火)

Description

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

,其中σ为均方差，$ar{x}$是各组数据和的平均值，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

Solution

一开始的做法是每次随机找一个数然后随机扔到一个数组里，然后加了一点优化
这样能跑到90……
因为温度高的时候状态十分不稳定，可以随机找一个数放到总和最小的组里
温度低的时候就随机找一个数随机放到一个组里
有些鬼畜的细节看代码吧……

Code

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<cstdio>
 5 #include<cmath>
 6 #include<algorithm>
 7 using namespace std;
 8 
 9 double eps=1e-1,minn=1e15,_x,ans;
10 int n,m,Belong[101],Sum[101],a[101];
11 
12 double Rand(){return rand()%10001+10000;}
13 
14 void Simulate_Anneal()
15 {
16     memset(Sum,0,sizeof(Sum));
17     for(int i=1;i<=n;i++)
18     {
19         Belong[i]=rand()%m+1;//Belong[i]第i个元素所属分组 
20         Sum[Belong[i]]+=a[i];//Sum[i]第i组元素的和 
21     }
22     ans=0;
23     for (int i=1; i<=m; ++i)
24         ans+=(Sum[i]-_x)*(Sum[i]-_x);//可以发现题目中式子的根号和分母对计算过程不影响，所以过程中可以只考虑分子 
25         
26     double T=10000;
27     while (T>eps)
28     {
29         int t=rand()%n+1,x=Belong[t],y;//t是随机的元素，x是t所属的分组，y是t将要分到的分组 
30         if (T>500)//温度高时往最小的组里扔 
31             y=min_element(Sum+1,Sum+m+1)-Sum;
32         else//否则随机一个 
33             y=rand()%m+1;
34         if (x==y) continue;//若x和y相同就重新选择 
35         
36         double preans=ans;
37         ans-=(Sum[x]-_x)*(Sum[x]-_x);
38         ans-=(Sum[y]-_x)*(Sum[y]-_x);
39         Sum[x]-=a[t],Sum[y]+=a[t];
40         ans+=(Sum[x]-_x)*(Sum[x]-_x);
41         ans+=(Sum[y]-_x)*(Sum[y]-_x);
42         
43         double delta=ans-preans;
44         if (delta<0 || exp(-delta/T)>Rand())
45             Belong[t]=y;
46         else
47         {
48             Sum[x]+=a[t]; Sum[y]-=a[t];
49             ans=preans;
50         }
51         if (ans<minn) minn=ans;//时刻更新全局最优解 
52         T*=0.9;
53     }
54 }
55 
56 int main()
57 {
58     scanf("%d%d",&n,&m);
59     for (int i=1; i<=n; ++i)
60         scanf("%d",&a[i]),_x+=a[i];
61     _x/=m;
62     for (int i=1; i<=10000; ++i) 
63         Simulate_Anneal();
64     printf("%.2lf
",sqrt(minn/m));
65 }