Beyond the Void
BYVoid
HAOI 2006 均分数据

看似简单的题,搜索是不行的。根据均方差的性质,要求分组后均方差最小,可以转化为平方之和最小的问题。即把N个数分为M组,使得每组平方的总和值最小。

一时没有想到更好的确定算法,我的方法是随机化+贪心调整。方法是最初先尽量平均地把N个数分为M组,然后随机调整10000次。每次调整选取两组a,b,用局部搜索的方法,确定这两组如何交换或给予一个元素才能使两者平方之和较小,按此调整。

该算法很大程度上取决于随机数的好坏,不能算是完美的算法。例如我srand不同的值,就有可能出现有些测试点不通过的现象。

/* 
 * Problem: HAOI2006 data
 * Author: Guo Jiabao
 * Time: 2009.3.26 13:43
 * State: Solved
 * Memo: 贪心 随机 调整
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=21,MAXM=7;
using namespace std;
struct group
{
	int E[MAXN],cnt,sum;
	double s;
}G[MAXM];
int N,M,sum,t;
double average,Ans;
int A[MAXN];
void init()
{
	int i,j,c,lj;
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
	scanf("%d%d",&N,&M);
	sum=0;
	for (i=1;i<=N;i++)
	{
		scanf("%d",&A[i]);
		sum+=A[i];
	}
	c=N/M;
	average=(double)sum/M;
	Ans=1e20;
	for (i=j=1,lj=0;i<=M;i++)
	{
		for (;j<=lj+c;j++)
			G[i].E[++G[i].cnt]=A[j];
		lj=j-1;
	}
	for (;j<=N;j++)
		G[1].E[++G[1].cnt]=A[j];
}
void out()
{
	Ans=sqrt((Ans/M));
	printf("%.2lf\n",Ans);
	exit(0);
}
void compute()
{
	int i,j;
	double t=0;
	for (i=1;i<=M;i++)
	{
		G[i].sum=0;
		for (j=1;j<=G[i].cnt;j++)
			G[i].sum+=G[i].E[j];
		G[i].s=(G[i].sum-average)*(G[i].sum-average);
		t+=G[i].s;
	}
	if (t<Ans)
		Ans=t;
}
void getpair(group *&A,group *&B)
{
	int a=rand()%M+1;
	int b=rand()%(M-1)+1;
	if (b==a) b=M;
	A=&G[a];B=&G[b];
}
inline int sqr(int a)
{
	return a*a;
}
void localsearch(group *a,group *b)
{
	int i,j,sa,sb,min=sqr(a->sum)+sqr(b->sum),t;
	int cx=0,ci,cj;
	if (a->cnt>1) // give a to b
	{
		for (i=1;i<=a->cnt;i++)
		{
			sa=a->sum-a->E[i];
			sb=b->sum+a->E[i];
			t=sqr(sa)+sqr(sb);
			if (t<min)
			{
				min=t;
				cx=1;
				ci=i;
			}
		}
	}
	if (b->cnt>1) // give b to a
	{
		for (i=1;i<=b->cnt;i++)
		{
			sa=a->sum+b->E[i];
			sb=b->sum-b->E[i];
			t=sqr(sa)+sqr(sb);
			if (t<min)
			{
				min=t;
				cx=2;
				ci=i;
			}
		}
	}
	//exchange
	for (i=1;i<=a->cnt;i++)
	{
		for (j=1;j<=b->cnt;j++)
		{
			sa=a->sum-a->E[i]+b->E[j];
			sb=b->sum+a->E[i]-b->E[j];
			t=sqr(sa)+sqr(sb);
			if (t<min)
			{
				min=t;
				cx=3;
				ci=i;
				cj=j;
			}
		}
	}
	if (cx==1)
	{
		b->E[++b->cnt]=a->E[ci];
		a->E[ci]=a->E[a->cnt--];
	}
	else if (cx==2)
	{
		a->E[++a->cnt]=b->E[ci];
		b->E[ci]=b->E[b->cnt--];
	}
	else if (cx==3)
	{
		t=a->E[ci];
		a->E[ci]=b->E[cj];
		b->E[cj]=t;
	}
}
void solve()
{
	int R;
	group *a,*b,*c;
	srand(1243);
	for (R=1;R<=1000;R++)
	{
		compute();
		getpair(a,b);
		if (a->sum > b->sum) {c=a;a=b;b=c;}
		localsearch(a,b);
	}
}
int main()
{
	init();
	solve();
	out();
	return 0;
}
<div class="MainText">

<strong>【问题描述】 </strong>
<p align="left">已知N个正整数:A1,A2,……,An。今要将它们分成M组,使得各组数据的数值和最平均,即各组的均方差最小。均方差公式如下:</p>

<div id="file" class="fullImageLink"><a href="http://www.ruvtex.cn/mw/images/8/8e/Data1.gif"><img src="http://www.ruvtex.cn/mw/images/8/8e/Data1.gif" alt="Image:Data1.gif" width="135" height="55" /></a> <a href="http://www.ruvtex.cn/mw/images/d/d4/Data2.gif"><img src="http://www.ruvtex.cn/mw/images/d/d4/Data2.gif" alt="Image:Data2.gif" width="77" height="49" /></a></div>
<p align="left">其中第一个公式是均方差,第二个公式是各组数据和的平均值,xi为第i组数据的数值和。</p>

<p align="left">【输入格式】
第一行是两个整数,表示N,M的值(N是整数个数,M是要分成的组数)。
第二行有N个整数,表示A1,A2,……,An。整数的范围是1--50。
<p align="left">(同一行的整数间用空格分开)</p>

<p align="left">【输出格式】
输出文件只有一行,包括一个数 ,表示最小均方差的值(保留小数点后两位数字)。

【输入样例】
6 3
1 2 3 4 5 6

【输出样例】

0.00

(1和6,2和5,3和4分别为一组)

【数据范围】

对于40%的数据,保证有K&lt;=N&lt;=10,2&lt;=K&lt;=6
对于100%的数据,保证有K&lt;=N&lt;=20,2&lt;=K&lt;=6</div>

上次修改时间 2017-05-26

相关日志