「HAOI2006」均分数据

发表于 | 分类于 | | 浏览量： 次

今天是国际劳动妇女节，各位妇女们有没有去劳动啊QwQ？反正我没去

传送门

洛谷P2503

BZOJ2428

题解

数据范围好小啊，看起来像是状压DP或者搜索之类的。蒟蒻我选择了模拟退火+贪心。

先考虑贪心，我们从$1$到$n$遍历整个序列，每次就把当前的元素丢到加和最小的那一组里。

显然光光这样贪心是肯定不行的，但是这样得到的答案还是比较优的。考虑怎样改进。

不难发现，如果遍历序列的顺序会影响最后的答案，那么可以考虑直接random_shuffle，打乱个比如$10^5​$次的，很大概率上就能刷到最优解了。

但是总感觉直接random_shuffle不太靠谱啊（不过貌似也能AC），但是蒟蒻我选择了模拟退火，感觉起来会靠谱一些（其实到底是不是更靠谱我也不知道，但是我想练一下模拟退火，所以就这样写了）。

每次随机拎出来两个元素交换，然后再计算当前答案就可以了。

代码

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
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=25,maxm=10;const double delta=0.991;
int n,m,A[maxn];double X[maxn],avg,ret,ans;
inline double Calc() //计算当前答案
{
	ret=avg=0;
	memset(X,0,sizeof(X));
	for(int i=1;i<=n;i++)
	{
		int mi=1;
		for(int j=1;j<=m;j++)
			if(X[j]<X[mi])
				mi=j;
		X[mi]+=A[i];
	}
	for(int i=1;i<=m;i++) avg+=X[i];
	avg/=m;
	for(int i=1;i<=m;i++) ret+=(X[i]-avg)*(X[i]-avg);
	return sqrt(ret/m);
}
inline void SA(double T)
{
	while(T>1e-12)
	{
		int a=rand()%n+1,b=rand()%n+1;
		while(a==b){a=rand()%n+1;b=rand()%n+1;}//rand出来两个是一样的概率挺大的，这样可以提升效率
		swap(A[a],A[b]);
		double now=Calc();
		if(now<ans) ans=now;
		else if(exp((ans-now)/T)<(double)rand()/RAND_MAX) swap(A[a],A[b]);
		T*=delta;
	}
}
int main()
{
	srand(20030909);           //黄霖的生日，种子什么的选大佬的生日肯定不会错的
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&A[i]);
	sort(A+1,A+1+n);
	ans=Calc();
	for(int i=1;i<=100;i++) SA(19630217);  //退火100次又不会WA并且还比较快，求稳的话可以多来几次
	printf("%.2lf\n",ans);
	return 0;
}