题目大意
已知$N$个正整数：$A_1,A_2,\ldots,A_n$。今要将它们分成$M$组，使得各组数据的数值和最平均，即各组的均方差最小。均方差公式如下：
其中$\sigma$为均方差，是各组数据和的平均值，$x_i$为第$i$组数据的数值和。
题目分析
模拟退火。
数据很强，专门卡了模拟退火，需要多次选择不同初始解进行退火，取较优解作为答案。（爬山算法还是能A，爬山已经无敌了）
每次退火的时候取出一个元素放入另一个集合计算代价。
话说如果省选来一道这样的题，想了半天最后考完标解说：“直接上模拟退火”，那不是很吃屎吗？
代码
爬山1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=25;
const double START_T=10000,END_T=1e-2,DELTA=0.9;
int n,m,a[maxn],Group[maxn];
double sum[maxn],ans=0,Ans=1e18,ave;
double sqr(double x) {
return x*x;
}
void Anneal() {
memset(sum,0,sizeof(sum));
for(int i=1; i<=n; i++) {
Group[i]=rand()%m+1;
sum[Group[i]]+=a[i];
}
ans=0;
for(int i=1; i<=m; i++)ans+=sqr(sum[i]-ave);
double t=START_T;
while(t>END_T) {
int tmp=rand()%n+1,x=Group[tmp],y=rand()%m+1;
if(x==y) {
t*=DELTA;
continue;
}
double tot=ans;
tot-=sqr(sum[x]-ave)+sqr(sum[y]-ave);
sum[x]-=a[tmp],sum[y]+=a[tmp];
tot+=sqr(sum[x]-ave)+sqr(sum[y]-ave);
if(tot<ans) {
ans=tot;
Group[tmp]=y;
} else sum[x]+=a[tmp],sum[y]-=a[tmp];
t*=DELTA;
}
Ans=min(Ans,ans);
}
int main() {
srand(99995999);
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++) {
a[i]=Get_Int();
ave+=a[i];
}
ave/=m;
random_shuffle(a+1,a+n+1);
for(int i=1; i<=850; i++)Anneal();
printf("%0.2lf\n",sqrt(Ans/m));
return 0;
}
退火1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=25;
const double START_T=10000,END_T=1e-2,DELTA=0.9,P=0.1;
int n,m,a[maxn],Group[maxn];
double sum[maxn],ans=0,Ans=1e18,ave;
double sqr(double x) {
return x*x;
}
void Anneal() {
memset(sum,0,sizeof(sum));
for(int i=1; i<=n; i++) {
Group[i]=rand()%m+1;
sum[Group[i]]+=a[i];
}
ans=0;
for(int i=1; i<=m; i++)ans+=sqr(sum[i]-ave);
double t=START_T;
while(t>END_T) {
int tmp=rand()%n+1,x=Group[tmp],y=rand()%m+1;
if(x==y) {
t*=DELTA;
continue;
}
double tot=ans;
tot-=sqr(sum[x]-ave)+sqr(sum[y]-ave);
sum[x]-=a[tmp],sum[y]+=a[tmp];
tot+=sqr(sum[x]-ave)+sqr(sum[y]-ave);
if(tot<ans||exp(-t/30000)<P) {
ans=tot;
Group[tmp]=y;
} else sum[x]+=a[tmp],sum[y]-=a[tmp];
t*=DELTA;
}
Ans=min(Ans,ans);
}
int main() {
srand(99995999);
n=Get_Int();
m=Get_Int();
for(int i=1; i<=n; i++) {
a[i]=Get_Int();
ave+=a[i];
}
ave/=m;
random_shuffle(a+1,a+n+1);
for(int i=1; i<=850; i++)Anneal();
printf("%0.2lf\n",sqrt(Ans/m));
return 0;
}
