题解 P2503 【[HAOI2006]均分数据】

2018-10-04 19:27:19


用模拟退火写过,交了两版才过qwq

于是用随机贪心写了一遍,结果几遍就过了qwq


大致思路是先random_shuffle,然后贪心。

贪心时可以将当前的数加入最小的一组中。

然后再循环个500000次,非常稳。

#include <bits/stdc++.h>
#define re register
#define sqr(x) ((x)*(x))
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int n,m,sum;
int a[30];
int x[10];
double ans=1000000000.0;
double ave;

inline void calc() {
    memset(x,0,sizeof(x));
    for (re int i=1;i<=n;i++) {
        int p=1;
        for (re int j=1;j<=m;j++)
            if (x[j]<x[p]) p=j;
        x[p]+=a[i];
    }
    double now=0;
    for (re int i=1;i<=m;i++) now+=sqr(x[i]-ave);
    now/=(double)m;
    if (now<ans) ans=now;
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;i++) a[i]=read(),sum+=a[i];
    ave=(double)sum/m;
    for (re int i=1;i<=500000;i++) {
        random_shuffle(a+1,a+n+1);
        calc();
    }
    printf("%.2f\n",sqrt(ans));
    return 0;
}