BZOJ 2428[HAOI 2006]均等データ

ソースリンク:http://www.lydsy.com/JudgeOnline/problem.php?id=2428
等分データ
Description
N個の正の整数が知られています.A 1、A 2、…、An.今はそれらをMグループに分けます.各グループのデータの数値と平均、つまり各グループの平均分散が最小となります.平均二乗平均の公式は以下の通りです.σ = Σi=1 M(x i−xρ)2 M\sigma=\sqrt{\fraac{\sum_{i=1}^M(x_{i}-\overline{x}^2{M}σ=MΣi=1 M(xi−x)2 xρ=Σi=1 M x i/overline｛x｝=\frac｛sum_{i=1}^M x｛M｝x=MΣi=1 M xiσ平均分散であり、x⑩overline｛x｝xは各グループのデータとの平均値であり、x＿i_｛i｝xiは第iグループのデータの値とする.
Input
1行目は2つの整数で、N、Mの値(Nは整数個数、Mはグループ数)の2行目はN個の整数があり、A 1、A 2、…、Anを表しています.整数の範囲は1–50です.(同じ行の整数間をスペースで区切る)
Output
この行には1つの数しか含まれていません.最小二乗平均の値を表します.
Sample Input
6 3
1 2 3 4 5
Sample Output
0.00
HINT
全てのデータに対して、K<=N<=20,2<=K<=6
問題を解く
アナログ焼なまし.登山アルゴリズムには多くの欠点があり、局部最適解に陥りやすく、自力で抜け出せないので、模擬焼なましは発見的に検索する時に、現在の解優がない場合にはまだ確率があります.登山アルゴリズムのように小山頂や尾根の両側を往復して揺れ動くことなく、局部最適解から逸脱する可能性があります.この問題では、まずランダムにデータを割り当てて、毎回ランダムに一つの要素を別のグループに移動します.移動後の分散が小さいなら、今回の移動を受け入れます.分散がもっと大きいなら、ランダムに一つの数を生成します.もしこの数が現在の温度より低いなら、大丈夫ですか?このようにして焼なまし初期の衝撃が大きい時に局所最適解から逸脱できることを保証し、時間が経つにつれて温度が低下し、最適解も徐々に正しい答えに近づいてきます.また、焼なましの初期は温度が高く、答えの揺れが大きいので、むやみに踊るのを避けるために、貪欲な策略を採用して、元素を現在の最小のグループに移動します.温度が低いと,最適解は正しい傾向にあり,またランダムに調整した.このようなでたらめな啓発式のアルゴリズムはもちろん一回が正しいことを保証することができなくて、比較的に保険のは10000+回の焼きなましを行うので、しかしRPのよくない博主は洛谷に交際します時WA 1つの点、ランダムな種を変えてAになりました.RPこそが王道であることを証明しています.orz.
コード

#include
#define db double
using namespace std;
const int M=25;
int x[M],sum[M],team[M],n,m;
db ave,minn=1e30;
db sqr(db x){return x*x;}
void in()
{
    srand(20021016);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    scanf("%d",&x[i]),ave+=x[i];
    ave/=double(m);
}
void sa()
{
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=n;++i)
    {
        team[i]=rand()%m+1;
        sum[team[i]]+=x[i];
    }
    db ans=0,T=10000,tmp;
    for(int i=1;i<=m;++i)
    ans+=sqr(sum[i]-ave);
    int j,f,t;
    while(T>0.1)
    {
        T*=0.9;
        j=rand()%n+1;
        f=team[j];
        if(T>500)t=min_element(sum+1,sum+1+m)-sum;
        else t=rand()%m+1;
        if(f==t) continue;
        tmp=ans;
        tmp-=sqr(sum[f]-ave);
        tmp-=sqr(sum[t]-ave);
        sum[f]-=x[j];sum[t]+=x[j];
        tmp+=sqr(sum[f]-ave);
        tmp+=sqr(sum[t]-ave);
        if(tmp<=ans) ans=tmp,team[j]=t;
        else if(rand()%10000>T) sum[f]+=x[j],sum[t]-=x[j];
        else team[j]=t,ans=tmp;
    }
    minn=min(ans,minn);
}
void ac()
{
    for(int i=1;i<=10000;++i)sa();
    printf("%.2lf",sqrt(minn/m));
}
int main()
{
    in();
    ac();
    return 0;
}