bzoj 2428: [HAOI2006]均分数据随机化

2021-10-18 22:44:03

2428: [HAOI2006]均分数据

Time Limit: 20 Sec Memory Limit: 256 MB

题目连接

http://www.lydsy.com/JudgeOnline/problem.php?id=2428

Description

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

,其中σ为均方差，是各组数据和的平均值，x_i为第i组数据的数值和。

Input

第一行是两个整数，表示N,M的值（N是整数个数，M是要分成的组数）

第二行有N个整数，表示A1、A2、……、An。整数的范围是1--50。

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

Output

这一行只包含一个数，表示最小均方差的值(保留小数点后两位数字)。

Sample Input

6 3
1 2 3 4 5 6

Sample Output

0.00

HINT

对于全部的数据，保证有K<=N <= 20，2<=K<=6

题意

题解：

随机化搞搞搞！http://www.cnblogs.com/rausen/p/4324676.html

代码：

//qscqesze

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define maxn 200001

#define mod 10007

#define eps 1e-9

int Num;

char CH[];

//const int inf=0x7fffffff;   //нчоч╢С

const ll inf=1e60;

/*

inline void P(int x)

{

    Num=0;if(!x){putchar('0');puts("");return;}

    while(x>0)CH[++Num]=x%10,x/=10;

    while(Num)putchar(CH[Num--]+48);

    puts("");

}

*/

inline ll read()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline void P(int x)

{

    Num=;if(!x){putchar('');puts("");return;}

    while(x>)CH[++Num]=x%,x/=;

    while(Num)putchar(CH[Num--]+);

    puts("");

}

//**************************************************************************************

double a[maxn];

int p[maxn];

int n,m;

double sum;

double ave;

double ans;

double sqr(double a)

{

    return a*a;

}

double solve()

{

    int cnt = , sum = , i;

    double tmp = , t1, t2;

    for (i = ; i <= n && cnt < m; ++i)

        if (sum + a[p[i]] >= ave)

        {

            t1 = sqr(sum - ave), t2 = sqr(sum + a[p[i]] - ave);

            if (t1 < t2)

                tmp += t1, sum = a[p[i]];

            else

                tmp += t2, sum = ;

            ++cnt;

        }

        else

            sum += a[p[i]];

    while (i <= n)

        sum += a[p[i++]];

    tmp += sqr(sum - ave);

    return tmp;

}

int main()

{

    //freopen("test.txt","r",stdin);

    n=read(),m=read();

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

    {

        a[i]=read();

        sum+=a[i];

        p[i]=i;

    }

    ave=sum/m;

    ans=-;

    int cntt=;

    while(cntt<)

    {

        random_shuffle(p+,p++n);

        if(ans==-)

            ans=solve();

        else

            ans=min(solve(),ans);

        cntt++;

    }

    printf("%.2lf\n",sqrt(ans/m));

}

码农公寓