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<=N<=10,2<=K<=6
對於100%的數據，保證有K<=N<=20,2<=K<=6</div>