题目描述

给你长度为的序列，需要你分成组，组内元素相加形成新的长度为的数组，询问数组最小的方差是多少。
方差公式:。

。

Solution

学到的新知识点，正经叫法好像是模拟退火，学到了还可以用随机数去解题。这个题目给出很小，我们可以模拟很多很多遍，虽然模拟全部最坏可以到每个数在每个位置都尝试一遍，，但是不需要那么多的枚举也可以出结果。因为我们涉及分组，要方差最小，就使得每一组数尽可能一样大，那么我们把原数组随机打乱，并且插入到个位置里面去，每次找到最小的哪个放进去，就会保证过程是最小的，那么再这些过程中，找到答案即可。时间的控制推荐使用代码允许时间，去卡一下。抄一下对拍的就行了。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 30 + 7;

int n, m;
double a[N], sum, avg, b[N], ans = 1e18;

void calc() {
    ms(b, 0.0);
    random_shuffle(a + 1, a + 1 + n);
    rep(i, 1, n) {
        int pos = min_element(b + 1, b + 1 + m) - b;
        b[pos] += a[i];
    }
    double tmp = 0.0;
    rep(i, 1, m) {
        tmp += (b[i] - avg) * (b[i] - avg);
    }
    tmp /= m;
    tmp = sqrt(tmp);
    ans = min(ans, tmp);
}

void solve() {
    n = read(), m = read();
    assert(n<=20);
    rep(i, 1, n)    a[i] = read(),assert(a[i]<=50), sum += a[i];
    avg = sum / m;
    //assert(n < 30);
    while ((double)clock() / CLOCKS_PER_SEC < 0.8)
        calc();
    printf("%.2f\n", ans);
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}