1. 题目还原与最初的想法为什么这是一道套娃优化题第一次见到【SCOI2010】传送带这道题是在备战省选那阵子。标题里带着省选二字不少人第一反应是畏惧可真正拆开之后你会觉得它考察的东西其实非常朴素平面上两条传送带一个人要从A点走到D点在AB传送带上速度是P在CD传送带上速度是Q在地面上速度是R问最短走多长时间。坐标范围很小绝对值不超过1000三个速度都是整数。看到这个数据范围第一反应就是这题根本不是让你用高深几何去精确构造的而是让你用基础算法里的二分、三分去做数值搜索。这也是湖南省选里很典型的一类题目——模型识别比算法本身更难。很多人第一眼的想法是传送带速度快那就尽量多走传送带呗。直接从A走到B再从B直线切到D或者反过来A直接直线走到C再走传送带到D。这两种极端的策略都容易计算却都错得离谱。因为AB、CD是两条有限长的线段不是无限延伸的多走传送带意味着可能绕路而绕路多出的地面距离会吃掉传送带的速度优势。真正的最优路径一定是一个混合策略从A出发沿AB走一段在某点E离开传送带走直线到CD上的某点F再沿CD走到D。于是总时间写成三项A到E的时间加E到F的时间加F到D的时间。1.1 路径模型的三个环节把路径拆成三段之后问题就变得非常算法化了。第一段在AB上传送带上行走速度固定为P第二段从E到F是地面直线速度固定为R第三段在CD上传送带上行走速度固定为Q。需要决策的只有两个点E在AB上的具体位置F在CD上的具体位置。这里有个关键细节E不一定要取在AB内部它可以是A点即完全不走AB传送带也可以是B点即走完整条AB同理F可以是C或D。最优解可能出现在端点这一点后面讨论三分边界时还要用到。如果不会参数化直接去二维平面里乱猜E和F的坐标这个题根本无解。但换个思路每条线段都可以用一个参数t∈[0,1]来表示E A t₁ × (B - A)F C t₂ × (D - C)。这样一来问题就变成了在两个一维区间[0,1]上各找一个最优参数。二维几何问题被压缩成了一维搜索问题这才是整道题的题眼。1.2 为什么贪心不成立先打破越快越好的直觉假设P10Q10R1视觉上地面速度极慢于是你倾向于多走传送带。可AB传送带和CD传送带之间的位置关系决定了直线切过去的代价。如果AB和CD相距很远你从B点下来走到D点这段地面距离可能要绕一大圈但如果你在AB上只走一小段提前下来走直线虽然传送带上走得少一些地面路程却缩短了。这就是一个典型的权衡问题传送带上多走一点地面路程可能减少也可能增加具体取决于两条线段的空间关系。这种权衡不是线性的无法用一个简单的比例去判断走多少最优所以贪心在这儿是行不通的。还有一个容易忽略的点题目里A到E的时间是距离除以PF到D的时间是距离除以Q但A到E的方向是从A出发沿AB方向走的不是任意方向飞过去的。也就是说第一段路径被约束在直线AB上第三段路径被约束在直线CD上。这两条约束线段可能相交、平行、共线、甚至退化成点。不同的几何关系会带来不同的单峰函数形态但三分解法对所有情况都保持稳定这也是它成为这道题标准解法的重要原因。1.3 从套娃结构看问题本质现在再回过头看整体结构外层需要选E内层需要选F。如果先把E固定住那么总时间关于F在CD上的位置是一个一元函数可以在[0,1]上做一次三分但E本身又需要我们决策于是外层再套一个三分。这就是所谓的三分套三分。它像俄罗斯套娃内层的搜索结果会作为外层函数的值返回。三维或更高维的类似问题也可以用同样的思路扩展只是复杂度会相应增加。这也是这道题被放在第1部分 基础算法提高篇--第2章 二分与三分里的原因——它不是一个偏题怪题而是把一维三分这个基础模型嵌套使用考察你对分治思想的理解是否透彻。2. 单峰函数与三分搜索解题的数学基础2.1 三分算法的基本原理二分的适用条件是单调性三分处理的则是单峰性。所谓单峰函数就是函数值先下降后上升单谷或先上升后下降单峰整个区间内只有一个极值点。传送带的时间函数恰好就是这种形态。三分搜索的具体过程是这样的假设当前搜索区间是[l, r]取两个三等分点m1 l (r-l)/3m2 r - (r-l)/3。计算f(m1)和f(m2)然后比较如果f(m1) f(m2)说明区间右侧离极值点更远可以把r收缩到m2如果f(m1) f(m2)说明左侧离极值点更远可以把l收缩到m1如果相等极值点在m1和m2之间任选一侧收缩即可通常同时把l移到m1、r移到m2也能保持正确性。每轮循环区间长度缩小为原来的2/3。虽然压缩速度不如二分的1/2但对于固定迭代次数来说收敛到double精度完全够用。关键在于比较f(m1)与f(m2)的大小这一步它要求函数必须是单峰的否则比较结果无法可靠地排除区间。2.2 为什么总时间函数是单峰的这是整道题最核心、也最容易被忽略的地方。很多人背了三分的模板却不知道传送带问题凭什么能套用。我从两个层面来说。第一层是内层固定E点后随着F从C向D移动距离EF的变化并不单调——如果F先靠近EEF先减小但当F越过了靠近E的最近点后继续向D移动EF又开始增大。与此同时F到D的距离单调递减。于是总时间中一项先减后增、一项单调减叠加出来的函数就呈现出单谷形态。第二层是外层让E从A向B移动时内层三分会为每个E算出最优的F这个最优值关于E的位置也是单谷的。直觉上E太靠近A传送带优势没充分利用E太靠近B又可能绕路太多中间某个位置能平衡这两方面。虽然严格的凸性证明涉及导数和二阶导数分析但竞赛里记住两条线段上的三分是安全的这个结论就足够了。有个小细节值得注意三层时间函数连续且分段平滑即使两条线段有特殊位置关系比如AB和CD相交、共线函数可能出现平台段——也就是一段区间内函数值完全相同。这种情况下f(m1)和f(m2)相等三分会收缩区间但依然能收敛到正确的结果只是可能停在平台内的某个点而不是唯一极值点。好在题目只要求输出最短时间不要求输出具体路径所以停在平台上的任何点都不影响答案。2.3 二分与三分什么时候用哪个二分解决的是单调问题典型例子是有序数组里的查找、二分答案验证可行性。比如做题时常见的二分查找找最先出现的某个值用的就是lower_bound思路如果当前值满足条件就往左找否则往右找每次缩小一半。三分解决的是单峰问题典型特征是不知道往左还是往右更优但可以通过比较中间两点来判断。有些读者可能会问既然三分也需要判断方向为什么不直接对E和F一起做二维三分理论上可以但二维三分的实现复杂度高而且容易因为两个维度的函数形态不一致而陷入局部极值。三分套三分的好处是内层对每个E都能精确求出该E下的全局最优F外层再对这个最优函数做三分逻辑上是严格正确的。带权二分则是二分的另一种高级形态我后面会单独展开。这里先记住一个经验法则如果题目是最小化某个值且该值关于决策变量是单峰的优先考虑三分如果题目是给定某个限制条件判断是否存在可行解优先考虑二分答案。3. 三分套三分完整代码实现与关键细节3.1 核心数据结构与输入处理这道题坐标是整数读入但计算时必须用double否则精度撑不到最后的两位小数。我习惯先写一个Point结构体再写一个参数化取点函数。#include cstdio #include cmath struct Point { double x, y; } A, B, C, D; double P, Q, R; double dist(Point a, Point b) { return sqrt((a.x - b.x) * (a.x - b.x) (a.y - b.y) * (a.y - b.y)); } Point getPoint(Point a, Point b, double t) { return {a.x (b.x - a.x) * t, a.y (b.y - a.y) * t}; }getPoint的作用很直接给定参数t∈[0,1]返回线段AB或CD上对应的坐标点。使用参数化的好处是任何时刻我们搜索的都是一个一维变量代码逻辑清晰也方便控制精度。3.2 内层三分在CD上找最优进入点F接下来写一个solveForE(E)它的任务是给定E点在CD上三分搜索使总时间最小的F。double totalTime(Point E, Point F) { return dist(A, E) / P dist(E, F) / R dist(F, D) / Q; } double solveForE(Point E) { double l 0, r 1; for (int i 0; i 100; i) { double m1 l (r - l) / 3; double m2 r - (r - l) / 3; Point F1 getPoint(C, D, m1); Point F2 getPoint(C, D, m2); if (totalTime(E, F1) totalTime(E, F2)) r m2; else l m1; } return totalTime(E, getPoint(C, D, l)); }注意这里的totalTime算的是从A出发、经过E和F、最终到达D的总时间而不仅仅是给定E到F的两段时间。因为有A到E和F到D这两项内层函数才不是单纯的距离函数目标函数形态才是单谷的。3.3 外层三分在AB上找最优离开点E主函数里对AB做同样的三分搜索唯一区别是每算一个m1和m2对应的函数值时都要调用一次内层solveForE得到该E下的最优总时间再进行比较。int main() { scanf(%lf%lf%lf%lf, A.x, A.y, B.x, B.y); scanf(%lf%lf%lf%lf, C.x, C.y, D.x, D.y); scanf(%lf%lf%lf, P, Q, R); double l 0, r 1; for (int i 0; i 100; i) { double m1 l (r - l) / 3; double m2 r - (r - l) / 3; Point E1 getPoint(A, B, m1); Point E2 getPoint(A, B, m2); if (solveForE(E1) solveForE(E2)) r m2; else l m1; } Point bestE getPoint(A, B, l); printf(%.2lf\n, solveForE(bestE)); return 0; }这段代码加在一起不超过60行是一份非常标准的三分套三分模板。我建议你把它背下来因为类似的结构会反复出现在其他单峰嵌套问题里。3.4 迭代次数不是玄学精度推导为什么循环100次而不是50次、200次或者用while(r-leps)我来算一笔账。最坏情况下搜索区间的初始长度是1参数区间每次三分后长度乘以2/3。循环100次后区间长度为(2/3)^100大约是2.46×10^-18。坐标范围是[-1000,1000]换算成实际距离这个误差已经远小于double能表示的精度更远小于题目要求的0.01秒精度。100次循环对于这道题的数据范围来说是绰绰有余的。还有一个细节外层每算一个点都要跑一遍内层100次三分外层本身100次加起来是100×10010000次totalTime计算每次计算只涉及一次sqrt、几次加减乘除即便是在古老的评测机上跑也是毫秒级别。省选题的时间限制一般不会卡这种复杂度所以你可以放心地把迭代次数设大一点。3.5 端点边界和退化情况的处理A和B可能重合C和D也可能重合。如果某条传送带的两个端点坐标相同getPoint返回的始终是同一个点三分搜索虽然在参数区间[0,1]上做但m1和m2对应的点完全相同函数值自然相同l和r会往中间收缩最终返回正确结果。因此不需要额外特判。不过有一个地方需要小心当你用getPoint(A, B, t)时如果A和B重合t没有任何意义getPoint返回的点就是那个重合点本身这在数学上是正确的因为传送带速度P只用于dist(A,E)/PEA时距离为0时间也为0。不会产生除零或NaN。另一个容易忽略的边界是最优解可能出现在EA、EB、FC、FD这些端点。三分搜索本质上不会漏掉端点因为l和r的初始值就是0和1每次收缩都会保留已包含候选点的区间端点始终在搜索范围内。这也是三分比某些枚举中间点的近似方法更可靠的原因。4. 精度、实测与常见翻车点4.1 输出精度那点事题目要求保留两位小数直接printf(%.2lf\n, ans)即可但我在实践中习惯给ans加上一个1e-9的微小正值再输出。原因是浮点数运算中真实最短时间比如12.3450000001double存储时可能变成12.3449999999直接四舍五入会输出12.34而正确答案是12.35。加一个1e-9可以把这种边界情况扶正。这种做法在竞赛中非常常见代价极小收益却很大。更稳妥的做法是ans 1e-9; 然后printf(%.2lf\n, ans);。这个技巧也被很多选手称为浮点修正量。虽然它不是这道题独有的但在需要输出实数的题目里它是性价比最高的一个细节。4.2 三分模板的两种写法与取舍网上流传的三分模板有两种。一种是上面这种固定迭代次数另一种是while (r - l eps)其中eps取1e-8或1e-10。我的建议是固定迭代次数原因有三点固定迭代次数的循环次数是确定的不会因为eps过小而陷入死循环eps的取值依赖坐标范围和数据特性主观性太强固定循环100次对性能的影响可以忽略不计但对精度的保证却是稳定可靠的。有些选手可能会担心如果题目坐标范围很大比如1e9100次迭代够吗答案是够的因为(2/3)^100约10^-18即使初始区间长度为1e9最终残余区间也只有1e-9远小于要求精度。真正该调整的不是迭代次数而是double的累计误差注意点——不过对于这道题放心用100次就好。4.3 实测中容易踩的坑函数值比较的稳定性用f(m1) f(m2)作为判断条件这在浮点数比较中其实是不安全的。m1和m2的函数值如果非常接近由于浮点误差比较结果可能出现随机波动导致收缩方向错误。但在三分问题里即使某一轮方向选择有误差后续若干轮仍然能把区间收缩到足够小最终结果依然正确。原因在于单峰函数的极值点周围函数值变化平缓方向选择的容错性很高。如果实在不放心可以这样改进当f(m1)与f(m2)的差的绝对值小于1e-12时直接同时把l设为m1、r设为m2既保留了正确性也避免了误差抖动。不过这种做法会略微降低收敛速度实际比赛里不需要过度设计。4.4 时间复杂度的整体估算这道题的时间复杂度是10^4量级的内外层三分乘积加上常数很小的距离计算完全可以在1秒内跑完。数据范围只有四个点和三组速度内存占用可以忽略不计。这类坐标小、只能靠搜索解决的问题时间复杂度的估算方式也暴露出一个信号它考验的是算法模型的识别能力而不是压常数的能力。5. 从这道题延伸出去二分三分的应用地图5.1 带权二分wqs二分到底是啥最近带权二分这个词在竞赛圈讨论度很高。它的正式名称是wqs二分解决的问题是一个最优化问题如果加上一个惩罚项可以让它在另一个维度上变成单调的于是可以通过二分惩罚系数来求最优解。举个例子有n个任务每个任务有完成时间和收益要求恰好分成k组使总收益最大。直接做要一维DP复杂度很高。带权二分的思路是给每多开一组加一个惩罚代价x然后问题变成分组数量不限的最优化问题。由于每多开一组会让总收益变差一点x越大最优分组数越少x越小最优分组数越多这样就建立起x和分组数量之间的单调关系可以二分x来逼近恰好k组的最优解。带权二分和三分本质上是两种不同的工具三分解决的是函数单峰问题带权二分解决的是惩罚系数加进去之后答案关于系数单调的问题它更多依赖单调性。很多同学把二者搞混其实只要抓住核心判断标准是单调还是单峰就不会错。5.2 单峰模型还能解决哪些经典题除了传送带还有一类经典题也靠三分解决有n个物品排成一排每个物品有一个位置你要选一个点放置仓库使所有物品到仓库的距离之和最小。如果距离是欧几里得距离这个函数是凸的可以直接三分最优位置。另一个常见场景是曲线拟合类问题给定一组点选一条水平线使各点到它的垂直距离之和最小这也是一个单峰函数可以三分。此外计算几何里求点到曲线的最近距离、凸函数求最大值也是三分的典型应用。其实只要函数连续且单峰三分的代码几乎不需要改动只要把f(x)的计算逻辑替换掉即可。这也是为什么我建议把三分写成模板函数用函数指针或lambda传入——它能让你在赛场上省下大量重复编码时间。5.3 省选题不难难在识别模型回过头来看【SCOI2010】传送带它最巧妙的地方就是把最短时间这种物理场景转化成一维参数的极值搜索问题。如果你被省选两个字吓住或者被传送带的物理外衣迷惑就会去尝试什么光的折射定律、费马原理、拉格朗日乘数法之类的几何推导不仅容易出错还会浪费大量时间。而一旦你认出两条线段上的两个决策点且目标函数单峰这道题就是送分题。我个人在实际练习中的体会是三分算法的实现难度只有一颗星但模型识别的难度能达到三颗星。每次做完新题我会刻意问自己三个问题——决策变量是什么决策变量的取值范围是不是一个连续区间目标函数在这个区间上是不是单峰或单调如果三个问题都是是那就可以直接用二分或三分暴力搜索省下来的时间去处理真正需要数学推导的地方。5.4 最后一个实用小技巧先写暴力验证再套三分我建议初学者在第一次写这类题时先写一个暴力枚举的版本——把AB和CD各自分成1000段枚举两个端点组合计算最短时间。虽然慢但可以当作标准答案来验证三分的正确性。我曾经用这个方法在一道竞赛模拟题上发现自己的三分函数写反了比较方向如果不做暴力对照那种错误几乎不可能靠肉眼发现。这道题整体思路清晰、实现量小、坑点集中非常适合作为二分三分章节的入门练习。做完之后再去找一两道带权二分相关的题目你对二分和三分这一章的理解会比死记模板强得多。