Beyond the Void
BYVoid
HAOI 2006 均分數據
本文正體字版由OpenCC轉換

看似簡單的題,搜索是不行的。根據均方差的性質,要求分組後均方差最小,可以轉化爲平方之和最小的問題。即把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

相關日誌