題目描述:
已知N個正整數:A1、A2、……、An 。今要将它們分成M組,使得各組資料的數值和最平均,即各組的均方差最小。均方差公式如下:
輸入輸出格式
輸入格式:
輸入檔案data.in包括:
第一行是兩個整數,表示N,M的值(N是整數個數,M是要分成的組數)
第二行有N個整數,表示A1、A2、……、An。整數的範圍是1–50。
(同一行的整數間用空格分開)
輸出格式:
輸出檔案data.out包括一行,這一行隻包含一個數,表示最小均方差的值(保留小數點後兩位數字)。
輸入輸出樣例
輸入樣例#1:
6 3
1 2 3 4 5 6
輸出樣例#1:
0.00
說明
樣例解釋:1和6、2和5、3和4分别為一組
【資料規模】
對于40%的資料,保證有K<=N <= 10,2<=K<=6
對于全部的資料,保證有K<=N <= 20,2<=K<=6
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int MAXN = ;
double mid ,ans;
int a[MAXN],p[MAXN],n,m;
double Pow(double x) { return x*x; }
double solve(){
int i,cnt=,sum=;
double t1,t2,ret=;
for(i=;i<=n&&cnt<m;i++){
if(sum+a[p[i]]>=mid){
t1=Pow(sum-mid);t2=Pow(sum-mid+a[p[i]]);//因為沒說每組資料個數強制相等
//在此處做一下取舍
if(t1<t2) ret+=t1,sum=a[p[i]];
else ret+=t2,sum=;
cnt++;
}
else sum+=a[p[i]];
}
while(i<=n) sum+=a[p[i++]];
ret+=Pow(sum-mid);
return ret;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
p[i]=i;
mid+=a[i];
}
mid/=m;ans=; int T = ;
while(T--){
random_shuffle(p+,p+n+);
ans=min(ans,solve());
}
printf("%.2lf\n",sqrt(ans/m));
return ;
}