隐藏
「HAOI2006」均分数据 - 爬山算法/模拟退火 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「HAOI2006」均分数据 - 爬山算法/模拟退火

题目大意

    已知$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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
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;
}

姥爷们赏瓶冰阔落吧~