[HAOI2006]均分数据

题意：
将n个数分成m组，求最小均方差？

思路：
随机打乱数组，然后贪心求结果，取最小值。
(double)clock()/CLOCKS_PER_SEC得出程序运行的时间，单位为S。
random_shuffle(a+1,a+n+1);打乱数组。
贪心策略：
前m个数每个数单独为一组，然后将剩余数分给当前最小数据和的组，可使用优先队列。

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll inf=1e9+7;

int a[100005];

struct w
{
    int i, p;
}w;

bool operator<(struct w a,struct w b)
{
    return a.p>b.p;
};

int main()
{
    int n, m;
    double sum=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum=sum+a[i];
    }
    sum=sum/m;
    double mi=inf;
    priority_queue<struct w> q;
    while((double)clock()/CLOCKS_PER_SEC<0.8)
    {
        for(int i=1;i<=m;i++)
        {
            w.i=i;
            w.p=a[i];
            q.push(w);
        }
        for(int i=m+1;i<=n;i++)
        {
            w=q.top();
            q.pop();
            w.p=w.p+a[i];
            q.push(w);
        }
        double pi=0;
        while(!q.empty())
        {
            w=q.top();
            q.pop();
            pi+=(w.p-sum)*(w.p-sum);
        }
        mi=min(pi,mi);
        random_shuffle(a+1,a+n+1);
    }
    printf("%.2f\n",sqrt(mi/m));
    return 0;
}