题目描述

已知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;

}

巴特西

HAOI2006 均分数据 [模拟退火]

题目描述

输入输出格式

输入输出样例

说明

题解

Code

博主蒟蒻,随意转载.但必须附上原文链接

http://www.cnblogs.com/real-l/

最新文章

热门文章