题目描述
已知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
题解
- 看到大部分人都写模拟退火+dp,但是我太蒻了,懒得dp(其实是不会),于是一波模拟退火+贪心调参最终A掉(心累)
- 这道题其实是不太好写的,因为题目只给了我们组数,需要我们自己分组,所以对于模拟退火来说,就只能随机分组
- 因为题目需要我们的均方差最小,这肯定需要我们有一个最优的分组,当温度较高时,答案还不是特别稳定,那么我们应该可以想到一个贪心,随机找一个元素,然后在整个分组中找一个当前总和最小的分组,把它加进去,再检查答案,如果当前更优,就更新,否则我们就以一定几率来接受它.而当温度较低时,这时答案已经比较稳定,即答案都差不多大,再使用贪心并没有多大作用,因此我们可以随机选出分组进行更新,更新方法还是和上面一样
- 因为模拟退火是随机算法,我们可以在时间复杂度允许的情况下运行多次,保证找到最优解
Code
#include<bits/stdc++.h>
#define in(i) (i=read())
using namespace std;
const double delta=0.98;
int read() {
int ans=0,f=1; char i=getchar();
while(i<'0' || i>'9') {if(i=='-') f=-1; i=getchar();}
while(i>='0' && i<='9') {ans=(ans<<1)+(ans<<3)+i-'0'; i=getchar();}
return ans*f;
}
int n,m;
double t,ave,minx=2147483647;
double sum[21];
int belong[21];
int a[21];
void work() {
memset(sum,0,sizeof(sum));
double ans=0,T=1024.0;
for(int i=1;i<=n;i++) {
belong[i]=rand()%m+1;
sum[belong[i]]+=a[i];
}
for(int i=1;i<=m;i++) ans+=(sum[i]-ave)*(sum[i]-ave);
while(T>1e-2) {
int t=rand()%n+1,x=belong[t],y;
if(T>35) y=min_element(sum+1,sum+1+m)-sum;
else y=rand()%m+1;
if(x==y) continue;
double preans=ans;
ans-=(sum[x]-ave)*(sum[x]-ave);
ans-=(sum[y]-ave)*(sum[y]-ave);
sum[x]-=a[t],sum[y]+=a[t];
ans+=(sum[x]-ave)*(sum[x]-ave);
ans+=(sum[y]-ave)*(sum[y]-ave);
if(ans<=preans) belong[t]=y;
else if(exp((ans-preans)/T)*RAND_MAX>rand()) {
sum[x]+=a[t],sum[y]-=a[t];
ans=preans;
}
else belong[t]=y;
T*=delta;
}
minx=min(ans,minx);
}
int main()
{
srand(time(0));
in(n); in(m);
for(int i=1;i<=n;i++) {
in(a[i]); ave+=a[i];
}
ave/=(double)m;
for(int i=1;i<=1024;i++) work();
printf("%.2lf\n",sqrt(minx/m));
return 0;
}