307. [HAOI2006] 均分数据

★★ 输入文件：data.in 输出文件：data.out 简单对比
时间限制：3 s 内存限制：128 MB

【问题描述】

已知N个正整数：A1，A2，……，An。今要将它们分成M组，使得各组数据的数值和最平均，即各组的均方差最小。均方差公式如下：

其中第一个公式是均方差，第二个公式是各组数据和的平均值，xi为第i组数据的数值和。

【输入格式】
第一行是两个整数，表示N，M的值（N是整数个数，M是要分成的组数）。
第二行有N个整数，表示A1，A2，……，An。整数的范围是1--50。

（同一行的整数间用空格分开）

【输出格式】
输出文件只有一行，包括一个数，表示最小均方差的值（保留小数点后两位数字）。

【输入样例】
6 3
1 2 3 4 5 6

【输出样例】

0.00

(1和6，2和5，3和4分别为一组)

【数据范围】

对于40%的数据，保证有M<=N<=10,2<=M<=6
对于100%的数据，保证有M<=N<=20,2<=M<=6

——————————————————————————————————————————————————————————————————————————

和上一题一样，模拟退火。

唯一区别在于不是两个调换位置，而是随机改变一个的归属。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int maxn=21;

int n,m,he;

double ping;

int a[maxn],belong[maxn],sum[maxn],sumf[maxn],belongf[maxn];

double ans;

double getans(int *sum)

{

    double tp=0;

    for(int i=0;i<m;i++)

    tp+=(ping-sum[i])*(ping-sum[i]);

    return sqrt(tp/m);

}

bool accept(double delta,double cur)

{

    if(delta<=0)return 1;

    return rand()<exp((-delta)/cur)*RAND_MAX;

}

double solve()

{

    const double maxw=10000;

    const double dec=0.999;

    double cur=maxw;

    double tpans=ans;

    while(cur>0.01)

    {

        int c=rand()%m,b=rand()%n;

        memcpy(belongf,belong,sizeof(belong));

        memcpy(sumf,sum,sizeof(sum));

        sumf[belongf[b]]=sumf[belongf[b]]-a[b];

        sumf[c]=sumf[c]+a[b];

        belongf[b]=c;

        double tp=getans(sumf);

        if(accept(tp-tpans,cur))

        {

            tpans=tp;

            memcpy(belong,belongf,sizeof(belong));

            memcpy(sum,sumf,sizeof(sum));

        }

        cur*=dec;

    }

    return tpans;

}

int main()

{

    freopen("data.in","r",stdin);

    freopen("data.out","w",stdout);

    srand(123645897U);

    scanf("%d%d",&n,&m);

    for(int i=0;i<n;i++)

    {

        scanf("%d",a+i);

        int tp=rand()%m;

        sum[tp]+=a[i];

        belong[i]=tp;

        he+=a[i];

    }

    ping=(double)he/m;

    ans=getans(sum);

    int t=150;

    while(t--)

    {

        ans=min(ans,solve());

    }

    printf("%.2lf",ans);

    fclose(stdin);fclose(stdout);

    return 0;

}

巴特西

COGS 307 模拟退火

307. [HAOI2006] 均分数据

最新文章

热门文章