HAOI 2006 均分数据
This post is written in Chinese. Please consider using Google Translate
看似简单的题，搜索是不行的。根据均方差的性质，要求分组后均方差最小，可以转化为平方之和最小的问题。即把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<=N<=10,2<=K<=6
对于100%的数据，保证有K<=N<=20,2<=K<=6</div>