算法模板（3）：搜索（5）：其他

搜索

模拟退火

• 模拟退火一个很关键的是，看看枚举到每一个方案是不是可能的。

3167. 星星还是树

• 在二维平面上有 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;
}

2680. 均分数据

• 已知 $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;
}

爬山法

• 爬山法必须是凸函数，而且是单峰的。
• 既然是凸函数为什么不用三分呢？

在多年的 OI 生活中，我意识到了，人类是有极限的，无论多么工于心计，绞尽脑汁，状态总是表示不出来的，出题人的想法总是猜不透的，边界总是写不对的——所以——我不三分了 JOJO！

一维函数需要一个三分，n 维函数需要 套用 n 个三分套用，复杂度是指数级别的。——闫学灿

• 其实这个东西不咋考

207. 球形空间产生器

• 给一个 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;
}

三分和二分

三分

• 把区间砍成三份，设中间两个分界点分别为$x_1=m_1,x_2=m_2$. 从左到右三段区间记为$L_1,L_2,L_3.$ 这里我们假设 $f(x)$ 是一个下凹的函数单峰函数，如果是上凸的函数，要学会转化。
• 那么，有两种情况：

1. 若 $f(m1)<f(m2)$，那么极值点一定不在 $L_3$ 这个区间，可以舍掉 $L_3$.
2. 若 $f(m1)\ge f(m2)$，那么极值点一定不在 $L_1$ 这个区间，可以舍掉 $L_1$.

浮点数三分

• 注：这个是有 $f$ 极小值的情况。

const double eps = 1e-8;
double f(m){//这里返回函数f(m)的值
}
double ternary_search(double l, double r){while(r - l > eps){double m1 = (l + r) / 2;double m2 = (m1 + r) / 2;if(f(m1) < f(m2)) r = m2;else l = m1;}return f(l);
}

整数三分

• 注：这个是 $f$ 有极小值的情况。

double f(m){//这里返回函数f(m)的值
}
int ternary_search(int lb, int ub){while (ub - lb > 1) {ll m1 = (lb + ub) / 2;ll m2 = (m1 + ub) / 2;ll f1 = f(m1), f2 = f(m2);if (f1 > f2) lb = m1;else ub = m2;}return min(f(lb), f(ub));
}

• 上面板子似乎有边界问题，我改了改

ll ternary_search() {ll lb = -2e17, ub = 2e17;ll res = min(f(lb), f(ub));while (ub >= lb) {ll m1 = (lb + ub) / 2;ll m2 = (m1 + ub) / 2;if (f(m1) >= f(m2)) lb = m1 + 1;else ub = m2 - 1;res = min(res, min(f(m1), f(m2)));res = min(res, min(f(lb), f(ub)));}return res;
}

二分

整数二分新写法

bool check(int x) {/* ... */} // 检查x是否满足某种性质// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
int bsearch_1(int l, int r)
{while (l < r){int mid = l + r >> 1;if (check(mid)) r = mid;    // check()判断mid是否满足性质else l = mid + 1;}return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_2(int l, int r)
{while (l < r){int mid = l + r + 1 >> 1;if (check(mid)) l = mid;else r = mid - 1;}return l;
}