BZOJ 2428 [HAOI2006]均分数据

题目大意

给你一个N个数的数列，让你分成M组使得均方差最小。

一看数据范围，肯定随机化水过！

对序列random_shuffle()之后这个问题变成了贪心问题。每次找到一个权值和最小的组把这个数放进去就好了qwq

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,a[30],cnt[7];
double sum,ans=1000000000.00;
int minn()
{
    int tmp=1;
    for(int i=1;i<=m;++i) if(cnt[i]<cnt[tmp]) tmp=i;
    return tmp;
}
double calc()
{
    double ret=0;
    for(int i=1;i<=m;++i) ret+=pow(cnt[i]-sum,2);
    return ret/m;
}
int main()
{
    srand(1026);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%d",a+i),sum+=a[i];
    sum/=m;
    for(int rt=1;rt<=500000;++rt)
    {
        random_shuffle(a+1,a+n+1);
        memset(cnt,0,sizeof cnt);
        for(int i=1;i<=n;++i) cnt[minn()]+=a[i];
        ans=min(ans,calc());
    }
    printf("%.2lf\n",sqrt(ans));
    return 0;
}