[HAOI2006]均分数据

随机的次数多了,代码轻松跑过.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,a[23],x[23];cin>>n>>m;double tot=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];tot+=a[i];
    }int T=1000000;tot/=m;double ans=0x3f;
    while(T--)
    {
        memset(x,0,sizeof x);
        random_shuffle(a+1,a+1+n);
        for(int i=1;i<=n;i++)
        {
            int id=1;
            for(int j=2;j<=m;j++)
            {
                if(x[j]<x[id])    id=j;
            }x[id]+=a[i];
        }double sum=0;
        for(int i=1;i<=m;i++)    sum+=(x[i]-tot)*(x[i]-tot);
        sum/=(double)m;
        ans=min(ans,sum);
    }printf("%.2f\n",sqrt(ans));
    return 0;
}