题目链接
读题意读了一年。。
题意是将n个数分成m组，将每个组的求一个sum。
计算m个sum的方差。求最小的方差。

思路：
先考虑连续选m个分组求最小方差，很容易想到DP。
dp[i][j]表示前i个数分成j组最小的花费。
状态转移就是 d p [ i ] [ j ] = m i n ( d p [ i ] [ j ] , d p [ k ] [ j − 1 ] + ( p r e [ i ] − p r e [ k ] − s u m / n ) ) ( k &lt; i , j &lt; = m ) dp[i][j] = min(dp[i][j], dp[k][j-1]+(pre[i]-pre[k]-sum/n))(k&lt;i, j &lt;= m) dp[i][j]=min(dp[i][j],dp[k][j−1]+(pre[i]−pre[k]−sum/n))(k<i,j<=m)
pre[i]表示前缀和，sum表示数组总和（因为均值一定：sum/n）
在考虑模拟退火，随机交换两个数，如果交换之后使能量减少，就可以交换，否则以一定几率交换。。套一套板子就行了。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ft first
#define sd second
#define all(c) ((c).begin()), ((c).end())
#define mp(a, b) make_pair(a, b)
#define pb(x) push_back(x)
const int maxn = 1e5+5;
typedef long long ll;
const ll mod = 1e9+7;
int Case = 1;
int n, m;
double a[maxn], pre[maxn];
double res = 1e18, t, sum;
double dp[100][100];
const double delta = 0.993;
double D(double x) {
    return x*x;
}
double cal_energy() { 
    for(int i = 1; i <= n; i++)
        pre[i] = pre[i-1] + a[i];
    memset(dp, 127, sizeof(dp));
    dp[0][0] = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            for(int k = 0; k < i; k++) {
                dp[i][j] = min(dp[i][j], dp[k][j-1]+D(pre[i]-pre[k]-sum/m));
            }
        }
    }
    return dp[n][m];
}
void simulate_anneal() {
    t = 2000;double nowres = res;
    while(t > 1e-14) {
        int x = 0, y = 0;
        while(x == y) x = rand()%n+1, y = rand()%n+1;
        swap(a[x], a[y]);
        double now = cal_energy();
        double new_delta = now-res;
        if(new_delta < 0) {
            res = nowres = now;
        }
        else if(exp(-new_delta/t)*RAND_MAX > rand()) nowres = now;
        else swap(a[x], a[y]);
        t *= delta;
    }
    // for(int i = 1; i <= n; i++) {
    // for(int j = 1; j <= n; j++) {
    // swap(a[i], a[j]);
    // res = min(res, cal_energy());
    // swap(a[i], a[j]);
    // }
    // }
}
void solve() {
    res = 1e10;sum = 0;
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
        cin>>a[i], sum+=a[i];
    while ((double)clock()/CLOCKS_PER_SEC<0.8) simulate_anneal();
    //cout<<res/m<<endl;
    if(res/m<1e-6) printf("0.00\n");
    else printf("%.2f\n", sqrt(res/m));
    return;
}
int main() {
    srand(rand());srand(rand());srand(rand());
    ios::sync_with_stdio(false);cin.tie(0);std::cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt","w",stdout);
#endif
    //scanf("%d", &Case);
    while(Case--){
        solve();
    }
    return 0;
}