首页 > 其他 > 详细

BZOJ2428: [HAOI2006]均分数据

时间:2018-07-13 00:45:22      阅读:26      评论:0      收藏:0      [点我收藏+]

标签:n+1   ()   空格   clu   小数点   define   包含   desc   mage   

BZOJ2428: [HAOI2006]均分数据

Description

已知N个正整数:A1、A2、……、An 。今要将它们分成M组,使得各组数据的数值和最平均,即各组的均方差最小。

均方差公式如下:

技术分享图片

Input

第一行是两个整数,表示N,M的值(N是整数个数,M是要分成的组数)
第二行有N个整数,表示A1、A2、……、An。整数的范围是1--50。
(同一行的整数间用空格分开)

Output

这一行只包含一个数,表示最小均方差的值(保留小数点后两位数字)。

Sample Input

6 3
1 2 3 4 5 6

Sample Output

0.00

HINT

对于全部的数据,保证有K<=N <= 20,2<=K<=6

题解Here!

懒得复制了,请戳

但是不得不说洛谷比BZOJ好多了。。。

至少可以看到怎么错了。。。

看着BZOJ上将近两页的提交记录,不是TLE就是WA啊。。。

是时候祭出这张图了:

技术分享图片

参数调试好累啊!!!

所以,代码稍稍改一下:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#define MAXN 25
using namespace std;
int n,m;
int belong[MAXN];
double average=0.00,minn=2147483645,val[MAXN],s[MAXN];
inline int read(){
	int date=0,w=1;char c=0;
	while(c<‘0‘||c>‘9‘){if(c==‘-‘)w=-1;c=getchar();}
	while(c>=‘0‘&&c<=‘9‘){date=date*10+c-‘0‘;c=getchar();}
	return date*w;
}
void SA(){
	double T=10000,ans=0.00;
	memset(s,0,sizeof(s));
	for(int i=1;i<=n;i++){
		belong[i]=rand()%m+1;
		s[belong[i]]+=val[i];
	}
	for(int i=1;i<=m;i++)ans+=(s[i]-average)*(s[i]-average);
	while(T>1e-4){
		double last=ans;
		int x=min_element(s+1,s+m+1)-s,y=rand()%n+1;
		ans-=(s[belong[y]]-average)*(s[belong[y]]-average)+(s[x]-average)*(s[x]-average);
		s[belong[y]]-=val[y];s[x]+=val[y];
		ans+=(s[belong[y]]-average)*(s[belong[y]]-average)+(s[x]-average)*(s[x]-average);
		if(ans<last||exp((ans-last)/T)*RAND_MAX<rand())belong[y]=x;
		else{
			ans=last;
			s[belong[y]]+=val[y];s[x]-=val[y];
		}
		T*=0.95;
	}
	minn=min(minn,ans);
}
void work(){
	for(int cases=1;cases<=5000;cases++)SA();
	printf("%.2lf\n",sqrt(minn/(double)m));
}
void init(){
	srand(2002);
	n=read();m=read();
	for(int i=1;i<=n;i++){
		val[i]=read();
		average+=val[i];
	}
	average/=(double)m;
}
int main(){
	init();
	work();
	return 0;
}

 

BZOJ2428: [HAOI2006]均分数据

标签:n+1   ()   空格   clu   小数点   define   包含   desc   mage   

原文:https://www.cnblogs.com/Yangrui-Blog/p/9302457.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号