洛谷P2503 [HAOI2006]均分数据(模拟退火)-白红宇

洛谷P2503 [HAOI2006]均分数据(模拟退火)

阅读量：6330 次

发布时间：2019-06-22

本文共 2027 字，大约阅读时间需要 6 分钟。

题目描述

已知N个正整数：A1、A2、……、An 。今要将它们分成M组，使得各组数据的数值和最平均，即各组的均方差最小。均方差公式如下：

输入输出格式

输入格式：

输入文件data.in包括：

第一行是两个整数，表示N,M的值（N是整数个数，M是要分成的组数）

第二行有N个整数，表示A1、A2、……、An。整数的范围是1--50。

（同一行的整数间用空格分开）

输出格式：

输出文件data.out包括一行，这一行只包含一个数，表示最小均方差的值(保留小数点后两位数字)。

输入输出样例

输入样例#1：

6 31 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

直接强上模拟退火

随机出每个位置在哪个地方

然后每次任意取出一个元素，加到最小的分组中

exp的设定就按套路来，用更新后的值减去之前的值

然后在BZOJ上T飞了

// luogu-judger-enable-o2#include
     
      #include
      
       #include
       
        #include
        
          #include
         
          #include
          
           #define sqr(x) ((x)*(x))const int MAXN = 31;const double eps = 1e-15;const int INF = 1e9 + 10;using namespace std;inline int read() { char c = getchar();int x = 0, f = 1; while(c < '0' || c > '9') { if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9') {x = x * 10 + c - '0';c = getchar();} return x * f;}int N, M;int belong[MAXN], a[MAXN];double sum[MAXN], Aver = 0, Best = 1e20;void MoNiTuiHuo() { memset(sum, 0, sizeof(sum)); const double DeltaT = 0.99; double ans = 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 += sqr(sum[i] - Aver); for(double T = 10000; T > eps; T *= DeltaT) { int P = min_element(sum + 1, sum + M + 1) - sum;//找出最小的位置 int X = rand() % N + 1;//这里直接随机就可以 double Pre = ans; ans -= sqr(sum[ belong[X] ] - Aver) + sqr(sum[P] - Aver); sum[ belong[X] ] -= a[X]; sum[P] += a[X]; ans += sqr(sum[ belong[X] ] - Aver) + sqr(sum[P] - Aver); if((ans < Pre) || (exp( (ans-Pre)/T ) * RAND_MAX < rand() )) belong[X] = P;//以一定概率接受最优解 else ans = Pre, sum[ belong[X] ] += a[X], sum[P] -= a[X]; //不更新 } if(ans < Best) Best = ans;}int main() { #ifdef WIN32 freopen("a.in", "r", stdin); #endif srand(19260817); N = read(); M = read(); for(int i = 1; i <= N; i++) a[i] = read(), Aver += a[i]; Aver /= M; for(int i = 1; i <= 1000; i++) MoNiTuiHuo(); printf("%.2lf",sqrt(Best / M));//因为y=sqrt(x)这个函数具有单调性，所以最后在开根就可以 return 0;}