• 在二维平面上有 n 个点，第 i 个点的坐标为 $(x_i,y_i)$。请你找出一个点，使得该点到这 n 个点的距离之和最小。
• 这个题如果是二维的话，其实是一个凸函数，我们可以用三分求解。

#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<ctime>#define x first
#define y secondusing namespace std;typedef pair<double, double> P;
const int maxn = 110;
P q[maxn];
int N;
double ans = 1e8;double rand(double l, double r) {//等概率得到区间的一个点return (double)rand() / RAND_MAX * (r - l) + l;
}double get_dist(P a, P b) {double dx = a.x - b.x;double dy = a.y - b.y;return sqrt(dx * dx + dy * dy);
}double calc(P p) {double res = 0;for (int i = 0; i < N; i++) {res += get_dist(q[i], p);}ans = min(ans, res);return res;
}void simulate_anneal() {P cur(rand(0, 10000), rand(0, 10000));//一开始可以把衰减系数定的大一些（0.999），边界条件定的小一些（1e-6），超时的话再调整for (double t = 1e4; t > 1e-4; t *= 0.99) {P np(rand(cur.x - t, cur.x + t), rand(cur.y - t, cur.y + t));double dt = calc(np) - calc(cur);//如果dt < 0，那么 if 里面的条件一定成立。//如果dt > 0，那么 if 里面的条件就是一个概率if (exp(-dt / t) > rand(0, 1)) cur = np;}
}int main() {scanf("%d", &N);for (int i = 0; i < N; i++) scanf("%lf%lf", &q[i].x, &q[i].y);for (int i = 0; i < 100; i++) simulate_anneal();printf("%.f\n", ans);return 0;
}

• 已知 $N$ 个正整数：$A_1、A_2、\dots \dots 、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}$$

• 过程是这样的：

1. 每次模拟退火都先随机打乱一下序列
2. 每次都尝试交换序列中两个数的位置，然后贪心地分组，每次都把当前的数放到当前每组的数之和最小地组里面去，然后看均方差是否变小，用这个方式模拟退火。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>using namespace std;const int maxn = 25, maxm = 10;
int N, M;
int w[maxn], s[maxm];
double ans = 1e8;double calc() {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;for (int i = 0; i < M; i++) avg += (double)s[i] / M;double res = 0;for (int i = 0; i < M; i++) {res += (s[i] - avg) * (s[i] - avg);}res = sqrt(res / M);ans = min(ans, res);return res;
}void simulate_anneal() {random_shuffle(w, w + N);//最开始的t和答案的范围有关。for (double t = 1e6; t > 1e-6; t *= 0.95) {int a = rand() % N, b = rand() % N;double x = calc();swap(w[a], w[b]);double y = calc();double delta = y - x;if (exp(-delta / t) < (double)rand() / RAND_MAX) {swap(w[a], w[b]);}}
}
int main() {scanf("%d%d", &N, &M);for (int i = 0; i < N; i++) scanf("%d", &w[i]);for (int i = 0; i < 100; i++) simulate_anneal();printf("%.2f\n", ans);return 0;
}

• 给一个 n 维空间的一个球，给 n + 1 个球上的点的坐标。求球心坐标。
• 这个题是可以用高斯消元写的。不过这里展现爬山法的写法。

#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;const int maxn = 15;
int N;
double d[maxn][maxn];
double ans[maxn];  //答案，即球心坐标
double dist[maxn], delta[maxn]; //每个点到球心的距离；每一维的偏移量。void calc(){double avg = 0;for (int i = 0; i < N + 1; i++){dist[i] = delta[i] = 0;for (int j = 0; j < N; j++)//求每个点到当前球心的距离dist[i] += (d[i][j] - ans[j]) * (d[i][j] - ans[j]);dist[i] = sqrt(dist[i]);//求所有点到球心距离的均值avg += dist[i] / (N + 1);}for (int i = 0; i < N + 1; i++)for (int j = 0; j < N; j++)//这个似乎是求的梯度。delta[j] += (dist[i] - avg) * (d[i][j] - ans[j]) / avg;
}int main(){scanf("%d", &N);for (int i = 0; i <= N; i++) {for (int j = 0; j < N; j++) {scanf("%lf", &d[i][j]);//圆心先初始化为所有点的算术平均值ans[j] += (d[i][j]) / (N + 1);}}//爬山法对精度非常严格，不然可能不收敛。for (double t = 1e4; t > 1e-6; t *= 0.99997) {calc();for (int i = 0; i < N; i++)ans[i] += delta[i] * t;}for (int i = 0; i < N; i++) printf("%.3lf ", ans[i]);return 0;
}