BZOJ2428——随机化贪心

本文主要是介绍BZOJ2428——随机化贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description
已知N个正整数：A1、A2、……、An 。今要将它们分成M组，使得各组数据的数值和最平均，即各组的均方差最小。均方差公式如下：
这里写图片描述
,其中σ为均方差，是各组数据和的平均值，xi为第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

这道题hzwer大佬打的是模拟退火，也有大佬打的是爬山。但是这些算法我都没有掌握，所以这题直接用随机化贪（乱）心（搞）。

这里要用到的是random_shuffle函数，这个函数的作用是将一个数组随机排列，我们将随机排列后的数组进行贪心，对于数组里的每一个树，都扔到当前总值最小的块里。这样有概率获得正解。当我们进行数十万次的random_shuffle，就有极大的概率获取正解。

#include<bits/stdc++.h>
using namespace std;
int read(){char c;int x;while(c=getchar(),c<'0'||c>'9');x=c-'0';while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0';return x;
} 
int a[25],b[10],n,m;
double ans,tot;
double sqr(double x){return x*x;}
double work(){memset(b,0,sizeof(b));for(int i=1;i<=n;i++){int id=1;for(int j=2;j<=m;j++) if(b[j]<b[id]) id=j;b[id]+=a[i];}double pl=0;for(int i=1;i<=m;i++){pl+=sqr(b[i]-tot);}pl/=m;return sqrt(pl);
}
int main()
{srand(2333333);ans=2e9;n=read();m=read();for(int i=1;i<=n;i++) a[i]=read(),tot+=a[i];tot=(double)tot/m;for(int k=1;k<=200000;k++){random_shuffle(a+1,a+1+n);ans=min(ans,work());} printf("%.2f",ans);return 0;
}