超市型网站开发,石家庄区号,优化官方网站设计,安全质量报监建设局网站Portal.
考虑一种随机贪心做法。为了让方差尽可能小#xff0c;要让每一组数的大小尽量接近。所以对于新的一个 a i a_i ai#xff0c;把它加入到当前的和最小的一组里。
为了提高正确性#xff0c;让分组的可能性变多#xff0c;我们随机 shuffle 这个序列#xff0…Portal.
考虑一种随机贪心做法。为了让方差尽可能小要让每一组数的大小尽量接近。所以对于新的一个 a i a_i ai把它加入到当前的和最小的一组里。
为了提高正确性让分组的可能性变多我们随机 shuffle 这个序列使答案更逼近正解。
注意方差要开根号。
#include bits/stdc.h
using namespace std;int a[25],b[25];
mt19937 rd(time(0));int main()
{int n,m;cinnm;int sum0;for(int i1;in;i) cina[i],suma[i];double xx(double)sum/m;double t1clock(),t2clock();double ans1e9;while((double)(t2-t1)/CLOCKS_PER_SEC0.95){shuffle(a1,an1,rd);memset(b,0,sizeof b);int minid1;for(int i1;in;i){for(int j2;jm;j)if(b[minid]b[j]) minidj;b[minid]a[i];minid1;}double tmp0;for(int i1;im;i) tmp(double)(xx-b[i])*(xx-b[i]);tmp/m,ansmin(ans,tmp);t2clock();}printf(%.2lf,sqrt(ans));return 0;
}
