M_sea

洛谷2503 [HAOI2006]均分数据
Luogu算法毒瘤模拟退火,我选择随机贪心。大致思路是先random_shuffle,然后贪心。因为我们要让每一组...
扫描右侧二维码阅读全文
01
2018/09

洛谷2503 [HAOI2006]均分数据

Luogu

算法

毒瘤模拟退火,我选择随机贪心。

大致思路是先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;
}
最后修改:2019 年 05 月 26 日 03 : 00 PM

发表评论