洛谷P2503 [HAOI2006]均分数据(随机化贪心)

现在来看这个题就是水题，但模拟赛时想了1个小时贪心，推了一堆结论，最后发现贪心做

不了，

又想了半个小时dp 发现dp好像也做不了，在随机化贪心和模拟退火

选了模拟退火但写炸了。(我怎么这么水)。我们来看这个题，采取

随机化贪心，利用random_shuffle函数将所有数字不停随机

化，每次

随机化后贪心的取就可以，因为采取的是随机化贪心，所以贪心策略不必最优，我们用x数组去存

储每个位置的值，枚举每一个数字，将数字加到最小的位置即可，我们已知最小位置的值一定小

于品均数，所以加到最小位置是较优的。

放代码吧

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<string>

#include<cstdlib>

#include<ctime>

#include<algorithm>

using namespace std;

const int maxn=1e4;

int n,m;

int a[maxn];

int x[maxn];

double xl,ans=0x3f3f3f3f;

void slove(){

	memset(x,0,sizeof(x));

	for(int i=1;i<=n;i++){

		int p=1;

		for(int j=1;j<=m;j++){

			if(x[j]<x[p])

				p=j;

		}

		x[p]+=a[i];

	}

	double cnt=0;

	for(int i=1;i<=m;i++){

		cnt+=pow(xl-x[i],2);

	}

	cnt=cnt/(double)m;

	ans=min(ans,cnt);

}

int main(){

//	freopen("a.in","r",stdin);

	scanf("%d%d",&n,&m);

	double add=0;

	for(int i=1;i<=n;i++){

		cin>>a[i];

		add+=a[i];

	}

	xl=add/m;

//	cout<<xl<<endl;

	int t=100000;

	while(t--){

		random_shuffle(a+1,a+1+n);

		slove();

	}

	ans=sqrt(ans);

	printf("%.2f",ans);

	return 0;

}

```P2503 [HAOI2006]均分数据 随机化贪心