P2503 [HAOI2006]均分数据
斯德哥尔摩
2018-07-12 21:58:40
[P2503 [HAOI2006]均分数据](https://www.luogu.org/problemnew/show/P2503)
题目要求：$$\sigma=\sqrt{\frac{\sum_{i=1}^m(x_i-\overline x)^2}{m}},\overline x=\frac{\sum_{i=1}^mx_i}{m}$$
把那个式子单独提出来：$\sum_{i=1}^m(x_i-\overline x)^2$
即：$\sum_{i=1}^m(x_i^2+\overline x^2-2x_i\overline x)$
拆开：$\sum_{i=1}^mx_i^2+n\overline x^2-2\overline x\sum_{i=1}^mx_i$
而我们知道，无论怎么分组，$\overline x$与$\sum_{i=1}^mx_i$都是不变的。
于是，问题就转化成了：求$\sum_{i=1}^mx_i^2$的最小值。
立马想起的是贪心与$DP$。。。
然而我们选择贪心。
为什么？因为$DP$的状态转移方程实在太难列，为了降低思维难度，选择贪心。
那么问题来了，如何贪心才能取到最优解？
于是，一种辅助贪心的算法横空出世——**模！拟！退！火！**
不知道的请戳[这](https://www.cnblogs.com/Yangrui-Blog/p/9296567.html)。
每次随机一个位置$i$，将这个位置的数字加到和最小的一组中，然后与当前最小值比较，更新即可。
这样，我们就可以极大概率的得到最优解。
注意：模拟退火的参数调试很烦人。。。
一个好的随机化种子界定了模拟退火的效率高低。。。
附代码：
```cpp
#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=200,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-10){
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.99;
}
minn=min(minn,ans);
}
void work(){
for(int cases=1;cases<=1000;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;
}
```