LuoGu P2503 [HAOI2006]均分資料

原題位址

比平衡點還裸的模拟退火模闆題，但是窩就是不會打，

太菜了

n個數分m組，讓方差最小，就是對于ai把ai放到最小的xi中（1<=x<=n）

對于n個數随機重組

退火很迷的我對着大佬的參數一個一個試下來（真開心嘤嘤嘤）

走好

// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
int n,m,a[25],grp[25],sum[25];
double ans,avg;
const double d = 0.992;
double get_val()
{
    double val = 0;
    for (int i = 1;i <= m;i++) 
        val += (sum[i] - avg) * (sum[i] - avg);
    return val / m;
}
void ch_grp(int pos,int target)
{
    sum[grp[pos]] -= a[pos];
    sum[target] += a[pos];
    grp[pos] = target;
}
void SA()
{
    double T = 3000,cur_ans = ans;
    while (T > 1e-10)
    {
        int pos = rand() % n + 1,target = rand() % m + 1;
        int origin = grp[pos]; 
        ch_grp(pos,target);
        double nans = get_val(),diff = nans - cur_ans;
        if (diff < 0)
        {
            cur_ans = nans;if (cur_ans < ans) ans = cur_ans;
        }
        else if (RAND_MAX * exp(-diff / T) <= rand()) ch_grp(pos,origin);
        T *= d;
    }
}
int main ()
{
    srand(time(0));
    scanf("%d%d",&n,&m);
    for (int i = 1;i <= n;i++) 
    {
        scanf("%d",&a[i]);avg += a[i];
    }
    avg /= m;
    for (int i = 1;i <= n;i++)
    {
        grp[i] = rand() % m + 1;sum[grp[i]] += a[i];
    }
    ans = get_val();
    for (int i = 1;i <= 1000;i++) SA();
    printf("%.2lf",sqrt(ans));
    return 0;
}
           

放棄吧，假的參數，我才不會給你真的呢。