BZOJ 2428 均分数据

发表于 | 更新于

Link

Solution

这种算法都是玄学 每次先random_shuffle来随机改变序列（好像并不能增加随机性？不管了反正本来就是玄学）

每次random地改动一个元素所在的集合，如果更优直接改掉； 否则，有一定的概率改掉，直观地想下，这个概率应该需要逐渐减小的（否则不就等于每次都无视之前所做的努力吗。。），由此就引入了温度的概念。 从初始温度开始模拟退火，每次循环的温度降低一些，接受不优解的概率是TT0\dfrac TT_0，通过随机数来实现。

Code

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
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=30;
using std::min_element;
using std::swap;
using std::random_shuffle;
template <class T> inline T sqr(T x){return x*x;}
int n,m,a[MAXN];double ANS=1e100,avg;
void Try()
{
	random_shuffle(a+1,a+1+n);
	static double sum[MAXN];static int bn[MAXN];
	memset(sum,0,sizeof(sum));
	double res=0;
	for(int i=1;i<=n;i++) sum[bn[i]=rand()%m+1]+=a[i];
	for(int i=1;i<=m;i++) res+=sqr(sum[i]-avg);
	int P=2e5;
	double Temper=P;
	while(Temper>1e-1)
	{
		Temper*=0.9;
		int cs,now,to;
		do	
		{
			cs=rand()%n+1,now=bn[cs],to=bn[cs];
			if(Temper>500) to=min_element(sum+1,sum+1+m)-sum;
			else to=rand()%m+1;
		}while(now==to);
		double temp=res;
		temp-=sqr(sum[now]-avg),temp-=sqr(sum[to]-avg);
		sum[now]-=a[cs],sum[to]+=a[cs];
		temp+=sqr(sum[now]-avg),temp+=sqr(sum[to]-avg);
		if(temp<res || rand()%P<Temper) bn[cs]=to,res=temp;
		else sum[now]+=a[cs],sum[to]-=a[cs];
	}
	chkmn(ANS,res);
}
int main()
{
	srand(522133279);
	get(n),get(m);
	for(int i=1;i<=n;i++) 
	{
		get(a[i]);
		avg+=a[i];
	}
	avg/=m;
	for(int loop=1;loop<=10000;loop++) Try();
	printf("%.2lf\n",sqrt(ANS/m));
	return 0;
}
/* AC Record(Bugs) *
 * 
 * * * * * * * * * */