luogu 2503 & bzoj 2428

两个多星期没更新了，显然我摸了两个星期的鱼

但我已经悔改了，我觉得就算天大的事情也不能让我放弃刷题去打lol，letme！让帝！不！！！!

完蛋了啊。我写了个假的爬山又A了(

先随机一些数的位置，然后考虑拿出来一个数字丢到sum最小的那里面即可。

#include <bits/stdc++.h>
using namespace std;
typedef double db;
const db eps = 1e-6;
const db delta = 0.90;
const db INF = 1e99;
int n,m;db a[22];db ave,ans = 1e18;
db sum[22];int pos[22];
db pow2(db x){return pow(x,2);}
void sa(){
    memset(sum,0, sizeof(sum));
    db now=0,T=100;
    for(int i=1;i<=n;i++)pos[i]=rand()%m+1,sum[pos[i]]+=a[i];
    for(int i=1;i<=m;i++)now+=pow2(sum[i]-ave);
    while (T*delta>eps){
        int id1 = min_element(sum+1,sum+1+m)-sum;
        int p = rand()%n+1,id2 = pos[p];
        if(id1==id2)continue;
        db tmp = now;
        now-=pow2(sum[id1]-ave)+pow2(sum[id2]-ave);
        sum[id2]-=a[p];sum[id1]+=a[p];
        now+=pow2(sum[id1]-ave)+pow2(sum[id2]-ave);
        if(now>tmp){//
            sum[id2]+=a[p];sum[id1]-=a[p];now=tmp;
        }else{
            pos[p]=id1;
        }
        T*=delta;
    }
    ans = min(ans, now);
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lf",&a[i]);
        ave+=a[i];
    }
    ave/=m;
    for(int i=1;i<=10000;i++) {
        sa();
    }
    printf("%.2f",sqrt(ans/m));
}