企业官网建设流程全解析

UVa 1524 Hot or Cold，第一次在 OJ 题目列表里看到这个标题时，我差点以为是玩猜温度的游戏。后来发现，这题的思路确实是让你去“猜”一个点，只是交互从游戏里的 hot/cold 提示，换成了函数的返回值。如果你正在刷 UVa 的老题，或者刚开始接触三分搜索，这道题非常适合作为第一道练手题。它没有复杂的图论和数据结构，代码量很短，但把单峰函数极值搜索的核心讲得很清楚。哪怕题面细节和我记忆里有些版本不太一样，算法骨架是通用的，理解之后就很难忘掉。

顺便说一句，搜题的时候容易被 MySQL 的 error 1524 (HY000): plugin 'mysql_native_password' is not loaded 干扰，那个是数据库认证插件的问题，跟 UVa 1524 这道算法题没有任何关系，别被搜到的数据库报错带偏。建议搜题时直接加 UVa 前缀，省得浪费时间。

1. 题目到底在考什么

1.1 从 hot/cold 游戏说起

小时候玩的猜物游戏是这样的：一个人把东西藏起来，另一个人在房间里找。离目标越近，旁观者会说 hot；越远，就说 cold。整个过程没有精确坐标，只有“近了”还是“远了”的反馈。放在算法里，就相当于有一个目标点 t，我们手里有个函数 f(x)，输入一个 x，它告诉我们 x 离目标有多近，或者更准确地说，是函数值距离最小值有多远。问题是：如何在不知道 t 的情况下，仅通过若干次 f(x) 的计算，快速把 t 找出来。

如果 f(x) 是单调的，那用二分就行。但如果 f(x) 是一个开口向上的抛物线，它在区间里只有一个最低点，这时你直接用二分的中点和端点比较，会发现左右两边都可能存在更低点，方向不好判断。这个时候要用三分搜索。UVa 1524 的核心考点就在这里：识别出目标函数在给定区间上是单谷的，然后用三分法逼近极小值点。

很多新手会纠结：为什么叫“Hot or Cold”却不叫“三分搜索”？其实题目名字就是在提示你，整个搜索过程就是靠“更热还是更冷”这种比较来收敛的。你算两个点的函数值，一个比另一个更接近极小值，这个点就更“热”，下一步就把搜索范围往它那边缩。想通了这一点，三分搜索就不再是死记硬背的模板。

1.2 我记忆里的 UVa 1524 输入输出

我印象中的 UVa 1524 题面大致是这样的：给定一个区间 [L,R]，再给定一个单谷函数 f(x) 的定义方式，要求输出区间内使 f(x) 取最小值的 x，保留三位小数。输入含有多组数据，读到文件尾结束。有些版本会把这个函数显式写成二次函数或绝对值函数，有些版本则只是告诉你有 n 个点，f(x) 是到这些点的距离平方和。

这种设定其实很适合用来练三分，因为函数本身并不复杂，重点全在搜索算法上。你不需要掌握什么高深的凸优化理论，只要能确认函数在给定区间里是“先减后增”的单谷形状，就可以放心三分。

这里多说一句：如果 f(x) 真的是到多个点的距离平方和，最优点其实就是这些点的平均值，直接求均值也能出答案。但作为算法练习，题目往往会要求你把 f(x) 当作黑盒来调用，不让你去推导数，这时候三分就是最直接、最稳妥的通用方法。以后遇到更复杂的单峰函数，你也能直接套。

1.3 为什么说这题适合新手

代码量小是它最大的优点。去掉头文件和输入输出，核心代码大概二十行左右。但就是这二十行，能练三件事：识别问题类型、写对三分边界、处理浮点输出。很多新手学完二分后看到三分会写错两个中点，也容易在浮点数循环条件上翻车，UVa 1524 刚好把这些坑都集中在一道题里，而且评测数据不算刁钻，适合用来建立信心。

我自己刷题有个习惯：遇到一个典型算法，先找一道老题 AC，再去看它的扩展变体。UVa 1524 就是典型的“算法入门三分题”，做完它再去做 Codeforces 上那些需要三分配合二分的题目，思路会顺很多。

2. 三分搜索：原理、写法与边界

2.1 三分搜索的数学基础

设函数 f(x) 在区间 [l,r] 上单谷，也就是先严格递减到极小值点，再严格递增。任取两个点 x1、x2，且 x1 < x2。比较 f(x1) 和 f(x2)：

• 如果 f(x1) < f(x2)，说明 x1 比 x2 更接近极小值，极小值不可能出现在 x2 右侧，所以新的搜索区间可以缩小到 [l, x2]。
• 如果 f(x1) > f(x2)，说明 x2 比 x1 更接近极小值，极小值不可能出现在 x1 左侧，所以新的搜索区间可以缩小到 [x1, r]。
• 如果 f(x1) == f(x2)，那极小值点一定在 [x1, x2] 之间，两边都可以缩，实际写代码时通常把区间缩到 [x1, x2]。

这个原理不需要求导，很多题直接给的是离散的点，导数根本不好求。这个比较方法非常像“Hot or Cold”游戏里通过温度方向来判断目标位置，每一步都能扔掉一部分区间。

需要注意，三分搜索要求函数是单峰的“单谷”或者“单峰”。如果函数有多个局部极小值，三分法只能找到一个，不能保证是全局最小。UVa 1524 的题目保证了这个性质，所以才能用。

2.2 两个三分点的取法与递推关系

标准的三分写法是把当前区间均分三段，取两个点：

• m1 = l + (r - l) / 3
• m2 = r - (r - l) / 3

这样 m1 和 m2 分别位于区间左三分之一和右三分之一处。比较 f(m1) 和 f(m2) 之后，无论走哪个分支，新区间长度都会变成原来的三分之二。因为如果保留 [l, m2]，m2 到 l 的距离是 (r-l) * 2/3；如果保留 [m1, r]，r 到 m1 的距离也是 (r-l) * 2/3。

迭代 n 次之后，区间长度缩小为初始长度的 (2/3)^n。指数函数收敛非常快，n=100 时精度远超过 double 能表示的范围。所以很多模板直接用固定迭代次数 100 次，而不是用 while(r-l>eps)，这能避免很多浮点比较的陷阱。

有人会问，能不能用 m1 = (l+r)/2，m2 = (l+r)/2 + 1e-7？这种情况其实是用一个极小的步长近似导数，然后用类似二分的思想判断朝哪边移动，并不算真正的三分。它的问题在于，如果函数在极小值附近非常平坦，小的步长可能导致两个函数值几乎相等，方向判断不稳定。标准三分取区间三分之一处的两个点，能保证每次稳定缩小 2/3，所以我还是推荐标准写法。

2.3 循环终止条件的正确姿势

写三分时最常见的错误是终止条件设置不当。我见过有人写 while (r-l > 1e-6)，结果在某些评测机上运行超时，或者因为浮点精度问题陷入死循环。原因很简单：浮点数在接近极限时，r-l 可能永远达不到 1e-6，或者达到之后还会因为舍入误差抖动。

更稳妥的做法是固定迭代次数，比如 100 次。double 的精度大约是 15-16 位十进制数，区间长度每次乘 2/3，迭代 100 次后区间长度约为初始长度的 (2/3)^100，大约是 2.5e-18，已经远小于 double 的精度极限，继续迭代没有意义。而且固定迭代次数不依赖具体区间大小，代码也更好写。

输出时一般要求保留三位小数，你其实也不需要太高的绝对精度，但多迭代几次不会错。如果你实在想用 while(r-l > eps)，至少把 eps 设成 1e-8 以下，并且加上迭代次数上限作为保险。

3. 完整 AC 代码与踩坑记录

3.1 可直接提交的 C++ 实现

以“给定区间 [L,R]，以及 n 个点，f(x) 为到这些点的距离平方和”为例，给出一个可直接提交的 C++17 代码。这个版本更适合用于理解三分搜索的流程，因为函数体一眼就能看明白。

#include <bits/stdc++.h> using namespace std; const int ITER = 100; vector<double> pts; double f(double x) { double res = 0; for (double p : pts) { double d = x - p; res += d * d; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; while (cin >> n) { pts.resize(n); for (int i = 0; i < n; i++) { cin >> pts[i]; } double l = -1e6, r = 1e6; // 根据题目实际范围调整 for (int it = 0; it < ITER; it++) { double m1 = l + (r - l) / 3.0; double m2 = r - (r - l) / 3.0; if (f(m1) < f(m2)) { r = m2; } else { l = m1; } } double ans = (l + r) / 2.0; cout << fixed << setprecision(3) << ans << "\n"; } return 0; }

这套模板的核心就是循环里的比较和区间收缩。只要确认 f(x) 是单谷函数，无论 f 具体长什么样，都可以直接替换掉函数体。很多题解里把这种写法叫“三分板子”，我建议你亲手敲三遍以上，敲熟为止。

3.2 踩过的三个坑

第一个坑是输出格式。C++ 里 setprecision(3) 必须和 fixed 配合使用，否则默认会输出有效数字位数，不是小数点后三位。比如 ans=3.14159，使用 setprecision(3) 会输出 3.14，而不是 3.142。题目要求保留三位小数时，一定要写成 fixed << setprecision(3)。

第二个坑是多组数据的读入。UVa 老题经常有多组测试数据，结束条件是 EOF。用 while(cin >> n) 是最稳的写法。不要用 while(scanf("%d",&n)!=EOF) 然后忘记处理换行符导致读入错位，也不要写成 while(true) 然后手动 break，容易漏读。

第三个坑是初始区间范围。二分和三分都要求初始搜索区间必须覆盖所有可能解。如果题目给的是 [-100,100]，你却写成 [0,100]，三分的收敛结果会被截断。我一开始做这道题时就是因为顺手把左边界设成 0，WA 了好几次。初始区间一定从题面里明确读出来，不要拍脑袋。

3.3 常见错误速查表

4. 本地测试与“搜题”避坑

4.1 用暴力枚举验证三分结果

三分写完最怕的是样例过了但不知道对不对。我通常会在本地写一个暴力枚举脚本，把区间切成几万个等分点，每个点都算一遍函数值，找到最小值位置，再和三分结果对比。这样能快速确认搜索方向有没有写反。

以刚才的“距离平方和”为例，Python 暴力验证可以这样写：

import math pts = [1.0, 2.0, 3.0] def f(x): return sum((x - p) ** 2 for p in pts) l, r = -1e6, 1e6 best_x, best_val = l, f(l) for i in range(1, 100001): x = l + (r - l) * i / 100000 val = f(x) if val < best_val: best_val = val best_x = x print("%.3f" % best_x)

如果三分程序和这个暴力枚举的结果一致，算法基本就对了。测试时可以故意把迭代次数改小到 10，生成一些肉眼可见的差异，观察收敛趋势，这样更容易理解三分每一步在干什么。

4.2 关于 error 1524 的题外话

在线搜索“UVa 1524”时，搜索引擎经常会带出 MySQL error 1524 相关的内容，比如 plugin 'mysql_native_password' is not loaded。这个错误是 MySQL 8.0 之后默认认证插件改为 caching_sha2_password 导致的，和算法题完全无关。如果你是因为做 UVa 1524 去搜这个数据库报错，大概率会越看越懵。

实际搜索时建议用更长的关键词，比如“UVa 1524 Hot or Cold solution three search”，或者直接去 UVa 的题解仓库里翻。老题的题解通常都很详细，多对比几份就能判断自己的理解对不对。

5. 从这道题学到的通用套路

5.1 三分搜索的经典变体

三分搜索不只是用在连续函数上，常见的变体有三类：

• 连续区间上的极值问题，比如这次讲的 UVa 1524。
• 整数定义域上的极值问题，比如求一个整数 k，使某个误差函数最小。因为三分点取整数时，m1 和 m2 可能靠得很近，循环终止条件要从“长度小于 eps”改成“长度小于 1”或者固定迭代次数。
• 参数化的二分答案问题，比如在一个单调函数上先二分出一个可行区间，再在区间内三分求最优解。

很多几何题也喜欢用三分。比如求一个点到平面曲线上某点的最短距离，如果曲线是凸的，距离函数往往单峰，可以三分角度参数。我在打区域赛时就遇到过一道类似的题，用三分直接秒掉，省下大量推导时间。

5.2 我在比赛中的实际应用

有一次现场赛我们卡在一道物理模拟题上，要求找一个发射角度，让炮弹落点离目标最近。那个函数导数不好推，而且参数范围很大。我第一时间想到三分，把发射角度当作自变量，落点距离作为函数值，先暴力枚举几个点判断函数是单峰还是单谷，确认后套上三分钟板子，十几分钟就调通了。

所以 UVa 1524 虽然是很老的题，但它教的三分思想在竞赛里非常实用。每当你看到一个目标函数，第一反应可以先画一画它是不是单峰/单谷，如果是，直接三分，别去硬推导数。这个习惯能让你省下大量时间。

如果你也在刷 UVa 1524，记住一点：先把函数在区间里是不是单谷确认清楚，再套模板。三分不是万能的，但用对地方非常香。

最后分享一个小技巧：调试时可以输出每次迭代的 l、r、f(m1)、f(m2)，观察区间是否在稳定缩小。如果发现某一步 l 和 r 不动了，多半是 f 的计算有问题，或者区间初始范围不对。这个观察习惯能避免很多玄学 WA，比反复猜评测数据强得多。