Luogu 均分数据

题解

题意

给出 $n$ 个数， 分成 $m$ 组，使得均方差最小

$$Ans = \sqrt{\frac{\sum_{i=1}^m(x_i - \overline x) ^ 2}{m}}$$
$$\overline x = \frac{\sum_{i=1}^{m} x_i}{m}$$
Ans 即为均方差

---

解

模拟退火

---

注意

退火时接受非最优解的条件
exp((NowAns - BefAns) / Now_tmep) * MAX_RAND < rand()

---

Code

#include <bits/stdc++.h>
const int N = 30; 
const double Delta = 0.99;
const double eps = 1e-10;
#define DB double  
int n, m, A[N], Bel[N];
DB Aver, Answer, Sum[N];
#define gc getchar()
inline int read() {
    int x = 0; char c = gc;
    while(c < '0' || c > '9') c = gc;
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;
    return x;
}
inline int Get_short() {
    int Min = 1e9, ret;
    for(int i = 1; i <= m; ++ i)
        if(Sum[i] <= Min) Min = Sum[i], ret = i;
    return ret;
}
DB Work() {
    DB NowAns = 0;
    for(int i = 1; i <= n; ++ i) Sum[i] = 0;
    for(int i = 1; i <= n; ++ i) Bel[i] = rand() % m + 1, Sum[Bel[i]] += A[i];
    for(int i = 1; i <= m; ++ i) NowAns += (Sum[i] - Aver) * (Sum[i] - Aver);
    DB Now_temp = 10000;
    while(Now_temp >= eps) {
        int shor = std:: min_element(Sum + 1, Sum + m + 1) - Sum, x = rand() % n + 1;
        DB BefAns = NowAns;
        NowAns -= (Sum[shor] - Aver) * (Sum[shor] - Aver) + (Sum[Bel[x]] - Aver) * (Sum[Bel[x]] - Aver);
        Sum[shor] += A[x];
        Sum[Bel[x]] -= A[x];
        NowAns += (Sum[shor] - Aver) * (Sum[shor] - Aver) + (Sum[Bel[x]] - Aver) * (Sum[Bel[x]] - Aver);
        if(NowAns < BefAns || (exp((NowAns - BefAns) / Now_temp) * RAND_MAX < rand())) Bel[x] = shor;
        else Sum[shor] -= A[x], Sum[Bel[x]] += A[x], NowAns = BefAns;
        Now_temp *= Delta;
    }
    return NowAns;
}
int main() {
    srand(20001206); //meizibaoyou
    n = read(), m = read();
    for(int i = 1; i <= n; i ++) A[i] = read(), Aver += A[i];
    Aver /= m;
    int Ty = 1000;
    Answer = 1e18;
    for(; Ty; Ty --) Answer = std:: min(Answer, Work());
    printf("%.2lf", sqrt(Answer / m));
    return 0;   
}