C++14(g++5.4) 解法, 执行用时: 75ms, 内存消耗: 476K, 提交时间: 2020-03-26 00:25:17

#include<bits/stdc++.h>
const int maxn = 30;
using namespace std;
double ans, now, f[maxn][8], ave;

int n, m, a[maxn],tot, sum[maxn];
inline double pow2(double x){ return x*x; }
double dp(){
    for(int i = 1; i <= n; ++i) sum[i] = sum[i-1] + a[i];
    for(int i = 0; i <= n; ++i) for(int j = 0; j <= n; ++j) f[i][j] = 0x3f;
    f[0][0] = 0;
    for(int i = 1; i<=n;++i)
        for(int j = 1; j <= min(i, m); ++j)
            for(int k = 0; k < i; ++k){
                f[i][j] = min(f[i][j], f[k][j-1]+pow2(sum[i] - sum[k] - ave));
            }
    return sqrt((1.0*f[n][m])/m);
}
void sa(double T){
    double eps = 1e-6;
    while(T > eps){
        int x = rand()%n+1, y = rand()%n+1;
        if(x == y) continue;
        swap(a[x], a[y]);
        double now = dp(), delta = now - ans;
        if(delta < 0 || exp(-delta/T) * RAND_MAX > rand())  ans = now;
        else swap(a[x], a[y]);
        T *= 0.999;
    }
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]), tot += a[i];
    ave = (tot*1.0)/m;
    ans = dp(); 
    sa(3000);//simulate annel
    printf("%.2lf\n", ans);
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 416ms, 内存消耗: 424K, 提交时间: 2023-04-17 21:40:44

#include<bits/stdc++.h>
using namespace std;
const int MAXN=20;
int a[MAXN+10];
int x[MAXN+10];
int main(){
    cout<<fixed<<setprecision(2);
    int n,m;cin>>n>>m;
    double sum=0;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        sum+=a[i];
    }
    sum/=m;
    double ans=1e9;
    int T=5e5;
    while(T--){
        random_shuffle(a+1,a+n+1);
        memset(x,0,sizeof(x));
        for(int i=1;i<=n;++i){
            int p=1;
            for(int j=1;j<=m;++j){
                if(x[p]>x[j])p=j;
            }
            x[p]+=a[i];
        }
        double y=0;
        for(int i=1;i<=m;++i)y+=(x[i]-sum)*(x[i]-sum);
        ans=min(ans,sqrt(y/m));
    }
    cout<<ans<<'\n';
}

C++(clang++11) 解法, 执行用时: 612ms, 内存消耗: 504K, 提交时间: 2021-01-24 21:42:55

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,a[23],x[23];cin>>n>>m;double tot=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];tot+=a[i];
    }int T=1000000;tot/=m;double ans=0x3f;
    while(T--)
    {
        memset(x,0,sizeof x);
        random_shuffle(a+1,a+1+n);
        for(int i=1;i<=n;i++)
        {
            int id=1;
            for(int j=2;j<=m;j++)
            {
                if(x[j]<x[id])    id=j;
            }x[id]+=a[i];
        }double sum=0;
        for(int i=1;i<=m;i++)    sum+=(x[i]-tot)*(x[i]-tot);
        sum/=(double)m;
        ans=min(ans,sum);
    }printf("%.2f\n",sqrt(ans));
    return 0;
}