p2503 [HAOI2006]均分数据

分析

random_shuffle一下

然后每次贪心的把当前点放进最小的组即可

这样做多次即可

代码

#include<bits/stdc++.h>
using namespace std;
#define lb double
lb ans=10000000000.0,p;
int n,m,a[110],sum[110];
inline lb work(){
    int i,j,k=1;
    lb res=0;
    memset(sum,0,sizeof(sum));
    for(i=1;i<=n;i++){
      for(j=1;j<=m;j++)
       if(sum[j]<sum[k])k=j;
      sum[k]+=a[i];
    }
    for(i=1;i<=m;i++)res+=(sum[i]-p)*(sum[i]-p);
    res/=(double)m;
    return res;
}
int main(){
    int i,j,k,tot=0;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)scanf("%d",&a[i]),tot+=a[i];
    p=(double)tot/m;
    for(i=1;i<=1000000;i++){
      random_shuffle(a+1,a+n+1);
      ans=min(ans,work());
    }
    printf("%0.2lf
",sqrt(ans));
    return 0;
}