北京西站出站口,广州黄埔区网站建设,字体怎么装到wordpress,网站html地图导航代码[HAOI2006]均分数据
题解#xff1a;
题目稍微解释一下#xff1a; 把n个数以分为m组#xff0c;计算每一组的和#xff0c;求得到的这m个数的方差。由于分法是任意的#xff0c;我们要求这些方差中的最小值 我们先用STL中的函数random_shuffle()用来对一个元素序列进行…[HAOI2006]均分数据
题解
题目稍微解释一下 把n个数以分为m组计算每一组的和求得到的这m个数的方差。由于分法是任意的我们要求这些方差中的最小值 我们先用STL中的函数random_shuffle()用来对一个元素序列进行重新排序随机的 众所周知如果每个组数的大小都相近的话方差就越小 所以我们每次将第i个数加给当前数之和最小的那个组这样操作可以使得在当前排列下m组数最相近也就是方差最小 循环个5e5次就够了太多就会超时5e6的话洛谷和牛客的机子都会超时 貌似dp也可以做
代码
#includebits/stdc.h
typedef long long ll;
using namespace std;
inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn100;
int a[maxn];
int x[maxn];
double tot;
double ans0x3f;
int n,m;
inline void calc()
{memset(x,0,sizeof(x));for(int i1;in;i){int p1;//第p组 for(int j1;jm;j){if(x[j]x[p])pj;}x[p]a[i];//每次把数加给最小的组 }double sum0;for(int i1;im;i){sumsum(x[i]-tot)*(x[i]-tot);}sumsum/(double)m;sumsqrt(sum);if(sumans)anssum;
}
int main()
{cinnm;for(int i1;in;i){cina[i];tota[i];}tot/(double)m;int T5000000;while(T--){random_shuffle(a1,a1n);calc();}printf(%.2f\n,ans);
}
