题目链接
2680. 均分数据
已知 \(N\) 个正整数：\(A_1、A_2、……、A_n\)。
今要将它们分成 \(M\) 组，使得各组数据的数值和最平均，即各组的均方差最小。
均方差公式如下：
\(\sigma = \sqrt{\frac{\sum_{i=1}^n(x_i - \bar{x})^2}{n}},\bar{x} = \frac{\sum_{i=1}^n x_i}{n}\)
其中 \(\sigma\) 为均方差，\(\bar{x}\) 为各组数据和的平均值，\(x_i\) 为第 \(i\) 组数据的数值和。
输入格式
第一行是两个整数，表示 \(N,M\) 的值（\(N\) 是整数个数，\(M\) 是要分成的组数）。
第二行有 \(N\) 个整数，表示 \(A_1、A_2、……、A_n\)。（同一行的整数间用空格分开）
输出格式
包括一行，这一行只包含一个数，表示最小均方差的值(保留小数点后两位数字)。
数据范围
\(M \le N \le 20\),
\(2 \le M \le 6\),
\(1 \le A_i \le 50\)
输入样例：
6 3
1 2 3 4 5 6
输出样例：
0.00
解题思路
模拟退火
将每个数放入某一组中有一个贪心策略：每次将该数放和最小的组中
这样的策略不一定能构造出答案，但是如果每次模拟退火将序列随机化就一定可以构造出答案，另外构造出的序列交换两点变化不大，即函数具有一定的连续性，故可用模拟退火求解
- 时间复杂度：\(O(随机)\)
代码
// Problem: 均分数据
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/2682/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
// %%%Skyqwq
#include <bits/stdc++.h>
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template <typename T> void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N=25,M=10;
int n,m,w[N],s[N];
double res=1e9;
double cal()
{
memset(s,0,sizeof s);
for(int i=0;i<n;i++)
{
int k=0;
for(int j=0;j<m;j++)
if(s[j]<s[k])k=j;
s[k]+=w[i];
}
double avg=0,ret=0;
for(int i=0;i<m;i++)avg+=(double)s[i]/m;
for(int i=0;i<m;i++)ret+=(s[i]-avg)*(s[i]-avg);
res=min(res,sqrt(ret/m));
return ret;
}
void aimulate_anneal()
{
random_shuffle(w,w+n);
for(double t=1e4;t>1e-4;t*=0.99)
{
int a=rand()%n,b=rand()%n;
double x=cal();
swap(w[a],w[b]);
double y=cal();
double delta=y-x;
if(exp(-delta/t)<(double)rand()/RAND_MAX)swap(w[a],w[b]);
}
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)cin>>w[i];
while((double)clock()/CLOCKS_PER_SEC<0.8)aimulate_anneal();
printf("%.2lf",res);
return 0;
}