AcWing 2680. 均分数据
原题链接
困难
作者:
3a5de52
,
2021-07-21 20:46:16
,
所有人可见
,
阅读 412
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<iomanip>
#include<climits>
using namespace std;
const double eps=1e-8;
const int N=22;
int n,m;
int op[N];
double get(vector<int> &f)
{
int sum=accumulate(f.begin(),f.end(),0);
double avg=1.0*sum/m;
double cnt=0;
for(int i=0;i<m;i++)
cnt+=(avg-f[i])*(avg-f[i]);
cnt/=m;
return cnt;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>op[i];
srand(20020216);
double T=100.0;
double detal=0.99995;
vector<int> pos(m);
for(int i=1;i<=n;i++)
{
int t=-1,u=0;
for(int j=0;j<m;j++)
{
if(t==-1||pos[j]<pos[t])t=j;
}
pos[t]+=op[i];
}
// for(int i=0;i<m;i++)cout<<pos[i]<<" ";
// cout<<"\n";
double now=get(pos);
double ans=now;
while(T>eps)
{
random_shuffle(op+1,op+1+n);
pos.clear();
pos.resize(m);
for(int i=1;i<=n;i++)
{
int t=-1,u=0;
for(int j=0;j<m;j++)
{
if(t==-1||pos[j]<pos[t])t=j,u=pos[j];
}
pos[t]+=op[i];
// if((double)clock()/CLOCKS_PER_SEC>0.8)break;
}
double _next=get(pos);
ans=min(ans,_next);
// cout<<ans<<" ";
T*=detal;
}
// cout<<"\n";
cout<<fixed<<setprecision(2)<<sqrt(ans)<<"\n";
return 0;
}