1. 这道“传送带”为什么值得反复咀嚼做信息学竞赛的同学应该都有这种感觉二分章节的题目大部分都是“在一个有序数组里找一个数”“在单调函数上找一个零点”套路很明显练几道就上手了。但1439这道【SCOI2010】传送带每次翻出来做都觉得当初的自己太天真——它表面上是个几何题实际考的是对二分和三分本质的理解尤其是“什么时候二分不够用、必须上三分”的判断力。我第一次做这题是在学完提高篇二分与三分之后当时看完题面直接懵了两根线段、三个速度、求最短时间这哪跟哪后来才知道这道题是省内选拔的经典老题被收录进基础算法提高篇无数次出现在各种训练列表里很多教练拿它当“二分与三分”章节的收尾题就是因为它的思维跨度足够大。这题适合谁做如果你刚学完三分、对单峰函数极值还不熟它是一道极好的巩固题如果你自认为二分三分已经滚瓜烂熟它也能让你重新审视一些细节。这篇东西我就把整道题从思路到实现从头到尾拆一遍包括踩过的精度坑、调试用的技巧、周边变式一次性讲清楚。1.1 先还原真实题面平面直角坐标系里有两条线段AB和CD。一个人从A点出发想到D点去。他在线段AB上走的速度是p在线段CD上走的速度是q在平面其他地方走的速度是r。注意这个“其他区域”指的是不在任何一条线段上的普通平面区域包含从AB下来到CD上去的中间那段路。问从A到D最短需要多少时间。输入给的是八个实数A、B、C、D四个点的坐标以及速度p、q、r。数据范围我记得大概是坐标绝对值不超过1000速度都是正实数。输出最短时间保留两位小数还是几位我记不太清反正这道题的精度要求在当时看来确实刁钻后面会说为什么。很多人第一眼会想这题是不是求一个折线路径A到AB上某点再到CD上某点最后到D没错因为如果出口点不在AB上那人在AB段外走的那一段速度是r如果进CD之前已经在CD上了那也不是最优的。理性分析就能发现最优路径一定长这样A出发在AB上走一段离开AB后在平面区域走直线到CD后再沿CD走到D。为什么中间必须是直线平面区域速度恒定两点之间直线时间最短这是费马原理的朴素版不需要证明直觉上就能接受。于是问题变成在AB上选一个点E在CD上选一个点F让dist(A,E)/p dist(E,F)/r dist(F,D)/q最小。两个变量两个约束看起来很简单但真正处理起来会发现E和F互相影响不是能独立优化的。1.2 核心难点双变量优化的拆解思路上面那个式子如果只有一个变量比如固定E求最优F那问题立刻简化成一个一维优化。但两个变量同时变化你没法直接“求导等于零”去解因为你连解析式都写不出来E和F都是二维坐标点。竞赛里处理这种双变量问题有一个非常经典的思路外层枚举一个变量内层对另一个变量做精确优化。具体到这道题就是外层三分E在AB上的位置内层三分F在CD上的位置。说白了对于AB上任意一个确定的E点内层三分能找到一个让总时间最小的F点而后把这个“最小时间”看成E的函数这个函数它是个单谷函数——这一点是整道题能做的理论基石也是需要证明或至少要有直观感受的。为什么外层函数的单谷性可以保证直观理解E从A慢慢走向B总时间先减小后增大。因为E太靠近A浪费了AB上的高速区间E太靠近BE到F的平面距离会过长。中间某个位置平衡了“在AB上利用高速”和“减少平面路程”时间最小。严谨证明需要用到凸函数复合的性质竞赛里通常接受这个事实但在心里要有数三分的正确性完全依赖这个函数是单谷的。2. 三分法原理再梳理为什么不用二分学二分的同学都熟悉一个场景f(x)单调可以二分找零点或找某个值。但如果函数不是单调的而是一个先减后增的碗形单谷或者先增后减的包形单峰二分就失效了——你不知道该往左走还是往右走。这时候三分就派上用场了。三分的思路非常直观。假设你在实轴上的区间[l, r]里找一个单谷函数的最小值点你取两个中间点m1 l (r-l)/3和m2 r - (r-l)/3然后比较f(m1)和f(m2)如果f(m1) f(m2)说明最小值点不可能在m2右边把右边界收缩到m2反过来最小值点不可能在m1左边把左边界收缩到m1每次迭代区间长度变为原来的2/3。如果你迭代60次(2/3)^60大约是2.5e-11量级配合双精度浮点精度完全够用。这就是为什么很多模板里直接写“循环60次”而不是判断r-l eps因为循环次数固定能避免死循环也更好控制误差。2.1 三分和“带权三分、整数三分”的区别很多同学在搜索引擎里搜“带权三分”或者“整数三分”我估计是被其他题目误导了。所谓“带权三分”其实不是特殊算法而是字面意思三分时函数值带权重比如求带权中位数之类的问题。而“整数三分”是在定义域是整数时用的。本题定义域是实数连续区间坐标比例可以任意取值所以直接用标准三分即可不需要额外的离散化处理。这里有一个容易犯迷糊的点Abel上的点怎么参数化用点的坐标(x, y)直接做三分变量行不行严格说可以但没必要而且容易出错——你三分x对应的y也变了这是一个直线上的约束关系函数值仍然是一维的但你没把这个约束显式表达出来写代码容易乱。更好的做法是用“比例”t ∈ [0, 1]表示从A出发沿AB走了全程的百分之多少。这样每个t唯一对应一个点而且三分区间固定是[0, 1]简洁清晰。这个参数化思路是我强烈建议新手养成的习惯在一条线段上找点时用一个归一化的比例值而不是直接操作坐标。后面所有计算都通过getPoint(A, B, t)这个函数返回坐标代码可读性和正确性都高很多。2.2 时间复杂度预估外层三分60次每次算calc(t)calc(t)内部又做60次内层三分。总计算量60 * 60 3600次函数求值每次求值涉及三四个距离公式也就是不到一万次sqrt运算。这个量级在竞赛环境下连零头都算不上跑得飞快。所以这道题别看思路绕实现起来计算量很小真正的难点在于把模型建对以及把三分套三分写成清晰不犯错的结构。3. 具体实现与核心代码说一下我用C从头实现这个题的全过程包括每一段的意图和容易出错的地方。代码我会分块解释不会一口气甩一大段让人自己啃。3.1 坐标点与距离函数#include bits/stdc.h using namespace std; struct Point { double x, y; }; double dist(Point a, Point b) { return sqrt((a.x - b.x) * (a.x - b.x) (a.y - b.y) * (a.y - b.y)); }这一段没什么好说的就是最基础的结构体加距离公式。注意用double而不是float这题的精度要求不允许你用单精度稍后细说。然后是关键的点在线段上按比例取位置Point getPoint(Point a, Point b, double t) { return {a.x (b.x - a.x) * t, a.y (b.y - a.y) * t}; }t0时返回At1时返回Bt0.5时是中点。用这个函数三分出来的t直接映射成点坐标干净利落。3.2 内层三分固定E求最优F接下来定义计算函数。先说内层给定AB上的E点在CD上找一个F点使得dist(E,F)/r dist(F,D)/q最小。注意这里为什么不含dist(A,E)/p因为在外层计算时E已经确定了这一项是常数不影响内层三分选择F。所以内层函数是double calcF(Point E, Point C, Point D, double q, double r) { double l 0, rT 1; for (int i 0; i 60; i) { double m1 l (rT - l) / 3.0; double m2 rT - (rT - l) / 3.0; Point F1 getPoint(C, D, m1); Point F2 getPoint(C, D, m2); double t1 dist(E, F1) / r dist(F1, D) / q; double t2 dist(E, F2) / r dist(F2, D) / q; if (t1 t2) rT m2; else l m1; } Point bestF getPoint(C, D, (l rT) / 2.0); return dist(E, bestF) / r dist(bestF, D) / q; }内层三分判断的是CD上的比例找到让“平面路程加CD内路程”最短的F点。我用了循环60次代替while (r-l eps)原因前面说了固定次数更稳不会因为eps设大了精度不够也不会因为eps设小了死循环。3.3 外层三分寻找最优E外层三分套上内层double solve() { // 已读入 A, B, C, D, p, q, r double l 0, rT 1; for (int i 0; i 60; i) { double m1 l (rT - l) / 3.0; double m2 rT - (rT - l) / 3.0; Point E1 getPoint(A, B, m1); Point E2 getPoint(A, B, m2); double t1 dist(A, E1) / p calcF(E1, C, D, q, r); double t2 dist(A, E2) / p calcF(E2, C, D, q, r); if (t1 t2) rT m2; else l m1; } Point bestE getPoint(A, B, (l rT) / 2.0); return dist(A, bestE) / p calcF(bestE, C, D, q, r); }整体结构就是外层三分枚举EE确定后内层三分完全求解F。三个速度都用上p在AB段q在CD段r在中间平面段。代码里三分的名字rT我用了rT而不用r避免和速度变量r冲突这个细节在写完整代码时非常重要变量名混乱是新手调试困难的一个主要来源。3.4 完整代码参考最终拼起来大概长这样我整理成一个可以直接提交的版本#include bits/stdc.h using namespace std; struct Point { double x, y; }; 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}; } double p, q, r; Point A, B, C, D; double calcF(Point E) { double l 0, rt 1; for (int i 0; i 60; i) { double m1 l (rt - l) / 3.0; double m2 rt - (rt - l) / 3.0; Point F1 getPoint(C, D, m1); Point F2 getPoint(C, D, m2); double t1 dist(E, F1) / r dist(F1, D) / q; double t2 dist(E, F2) / r dist(F2, D) / q; if (t1 t2) rt m2; else l m1; } Point bestF getPoint(C, D, (l rt) / 2.0); return dist(E, bestF) / r dist(bestF, D) / q; } double calcE(double t) { Point E getPoint(A, B, t); return dist(A, E) / p calcF(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, rt 1; for (int i 0; i 60; i) { double m1 l (rt - l) / 3.0; double m2 rt - (rt - l) / 3.0; double t1 calcE(m1); double t2 calcE(m2); if (t1 t2) rt m2; else l m1; } printf(%.2lf\n, calcE((l rt) / 2.0)); return 0; }我补充一个个人习惯把外层主干写成一个循环内层逻辑全部封装成函数这样主函数非常干净。如果比赛时时间紧张直接套这个模板改改函数名就能用。4. 精度控制与边界情况的实战经验这道题最坑的不是思路是精度。下面几条是我实际写起来踩过或者见过别人踩的坑单列一节希望能帮你少走弯路。4.1 eps到底设多少很多同学习惯写while (r - l 1e-6)在这题上可能出问题。因为三层运算叠加外层三分内层三分距离计算误差是会累积的。我实测过如果内层用1e-6作为终止条件外层也用1e-6在一些极限数据下答案可能差到0.01以上刚好卡在输出精度边界非常被动。稳妥做法是内层外层都用固定循环次数。我一般用60次迭代。为什么是60因为(2/3)^60 ≈ 2.46e-11这个精度远小于双重浮点数的极限精度足够用了。就算比赛环境下的double精度是15位十进制数60次迭代也把区间压到了极限再多迭代也不会有收益。如果你非要用while写法建议eps用1e-12甚至更小但要注意在极端情况下可能出现浮点数无法继续缩小的死循环所以循环次数上限还是得加。这就回到了“固定次数”更稳妥的结论。4.2 数据范围的边界AB或CD退化成一个点题目没说AB和CD一定是非退化的线段。如果A和B完全重合或者C和D完全重合三分照样能跑——因为区间[0,1]上的所有点都映射到同一个坐标计算出来时间一样三分不会出错。但有一个地方需要小心如果CD退化成一个点内层三分的对象是恒定值仍然能正常运行如果AB退化成一个点外层三分也同理。我测试过代码在这两种退化情况下都能给出合理答案。但如果你输出精度要求高退化情况下直接返回dist(A,D)/r当AB和CD都退化成点人也只能走平面也可以特判不过这属于锦上添花不特判一般也不会挂。4.3 三分区间必须是 [0,1]由于我们用比例参数区间天然是[0,1]。但有的同学会想直接三分E点的x坐标不也行吗如果AB是竖直线x坐标恒定三分就废了。所以再次强调比例参数化的优越性无论线段方向如何始终是一维区间上的问题三分稳定。如果你在别的问题里三分的是一个几何点的某个坐标一定要先确认这个坐标和线段位置是一一映射且不退化否则可能踩坑。4.4 使用C17或更高版本编译代码里用了{a.x ..., a.y ...}这种聚合初始化结构体在C11及以后都支持。如果评测机是老古董编译器可能需要改成构造函数。这个细节看起来不值一提但我真有朋友因为本地C17能过、评测机C98直接ce的惨痛经历所以提醒一句。5. 常见问题与排查技巧整理一下我在这道题上遇到的典型问题以及和同学讨论时发现的高频错误。问题表现可能原因解决方案答案比标准答案大很多内层三分迭代不够或eps过大全部改成固定60次循环答案是0.00变量名r冲突导致读入错误或不正确检查变量命名区分速度r和区间右端点答案在样例上正确但大数据WA速度p、q、r直接相加时距离公式写错逐项检查dist公式尤其是坐标嵌套跑不出来或超时三分写成了while(r-l1e-3)导致循环次数过多改成固定迭代次数输出精度不对printf用了%f而不是%.2lf用printf(%.2lf, ...)或cout fixed setprecision(2)除了表格里的我再讲一个很隐蔽的bug外层三分里计算t1时dist(A, E1) / p这一项有的同学会写成dist(A, B) / p再乘以比例。这两种写法是一样的但如果你混用了不同比例比如用m1的E点却用m2的路径时间那答案绝对错。这种错误非常隐蔽样例数据简单时很可能测不出来建议写完后在草稿纸上手动推一两个点验证。还有一个高频问题盲目套“三分求极大值”模板。有些讲义上三分模板是求最大值的判断条件写反直接抄过来最小值就变成了最大值。我建议每次写三分前默写一遍判断逻辑别偷懒如果是求最小值f(m1) f(m2)说明右边可以缩掉求最大值则相反。这个方向和函数“碗形/包形”是对应的理清楚再写别硬背。6. 延伸思考这类“套娃三分”还能用在哪这题做完之后我觉得最值的不是学会套路而是吃透“把嵌套问题拆成多个独立子问题”的思路。后面我在别的地方遇到不少相似的题比如离线决策类DP、几何最短路径规划本质都是这种“外层选一个决策内层对另一个决策做精确求解”的结构。稍微扩展一下如果传送带的路径不是一条线段而是一段圆弧三分照样可以用——前提是参数化后目标函数仍然单峰。不过圆弧上的参数化就不能用简单的比例了得用圆心角。另一个变式如果中间平面区域速度也是变化的比如存在障碍物问题就直接升级成最短路加连续优化性质会被打破三分就不能硬用了。这些延伸题我先不展开但你做这道题时如果能养成“为什么单峰”“区间缩小的依据是什么”这样思考的习惯后面进步会快很多。我个人做算法题最大的心得就是一道好题值得反复咀嚼把每个“理所当然”的点都抠一遍才能真正变成自己的东西。