做二分三分的练习题时最怕遇到哪种题就是把模板背得滚瓜烂熟但看到题目根本不知道该往哪个方向套。SCOI2010这道“传送带”就是这个类型的典型代表。它出现在基础算法提高篇的二分与三分章节里题目本身并不长但如果你只会二分查找模板第一次看到基本都会卡住这题既没有单调数组让你查也没法直接二分答案它要的是在一个平面上找两个点让总时间最短。我当时做这道题的时候第一反应是用几何方法硬推推了半天发现情况特别多最后老老实实回去学三分才明白出题人把它放在这一章的用意。这道题的核心价值在于它用最直观的方式展示了“单峰函数为什么可以三分求解”而且是一个经典的“嵌套三分”模型。整道题没有复杂的算法结构代码量也很小但背后的思路转换非常关键。这篇文章我会把从题意拆解、单峰性论证、公式推导到最终AC代码、调试避坑完整讲一遍适合刚学完二分、准备向三分进阶的竞赛选手参考。1. 这题到底在问什么传送带模型与最优化目标1.1 题意拆解与变量定义先看原题模型。平面上有两条线段AB和CDA、B两点之间有一条传送带C、D两点之间也有一条传送带。一个人在平地上行走的速度是q在传送带AB上行走的速度是p在传送带CD上行走的速度是r。这个人要从A点出发最终到达D点他可以先在AB传送带上走一段然后下传送带在平地上走一段再上传送带CD走一段最后到达D。题目要求的是这个人应该怎么规划路径使得总时间最短。这里的路径不是随意曲线而是被约束成“三段走法”在AB上从A走到某个点E从E直线走到CD上的某个点F再从F走到D。为什么中间一定是直线因为平地上没有任何速度差异两点之间直线最短所以E到F必然走直线段。把变量说清楚E在线段AB上F在线段CD上。我们需要同时确定E的位置和F的位置使得[ T \frac{|AE|}{p} \frac{|EF|}{q} \frac{|FD|}{r} ]最小。注意三个速度的单位要一致题目给的是速度所以时间是路程除以速度。有些题目给的是“单位路程花的时间”那种情况就要反过来乘这是读题时需要分辨的细节下面避坑部分还会单独说。很多人拿到这个题会想E和F不都是直线吗直接让E到F的连线经过两个传送带之间最短连线不就行了问题在于两条传送带上的速度不同平地速度也可能不同所以“几何最短”并不等于“时间最短”。当传送带速度比平地快很多时你愿意在传送带上多走一段哪怕绕一点点路当传送带速度慢时你恨不得刚上就下。这个“权衡”本质上就是一个最优化问题而不是一个纯几何问题。1.2 为什么暴力枚举和贪心都不可行最容易想到的办法是枚举。E和F都是连续变量你不可能真的枚举所有点。退一步把每条线段均匀切成很多小段用双重循环暴力找最优误差取决于切分密度。切1000段就是10^6次计算每次还要算距离和除法精度还只能到千分之一显然不靠谱。切1e5段就是10^10次直接超时。也有人想贪心先让E取某个特殊点比如A或者B然后求F。但这条路也不通因为E的取值会影响F的最优位置两个变量耦合在一起不是独立决策。比如E在A点时最好的F可能是靠近C的E在B点时最好的F可能就变成靠近D的。你没法先定一个再推另一个。这种“两个连续变量互相影响又都要在固定范围内选值”的问题就是一个典型的“区间内找函数极值”问题。如果函数具有单调性可以二分如果函数是单峰的就可以三分。传送带这道题的精髓就在于它把单峰函数从一维常识题升级成了二维嵌套题逼迫你把三分算法真正理解透。2. 为什么非要用三分单峰函数决定了算法走向2.1 三分和二分到底差在哪二分查找能在有序数组里快速找目标值依赖的是“单调性”。你把区间一分为二根据中点和目标值的大小关系能确定答案在左半边还是右半边。但最优化问题里函数往往不是单调的而是先下降后上升或先上升后下降这种情况没有单调性可用但满足“单峰性”。三分算法就是把区间分成三段不是找中点而是找两个三分点m1和m2。比较f(m1)和f(m2)的大小就能判断峰的位置在哪一侧。以“极小值”为例假设函数先下降后上升如果f(m1)小于f(m2)说明m1更接近谷底那么谷底位于m2的左侧右边界就可以收缩到m2反过来如果f(m1)大于f(m2)说明m2更接近谷底谷底位于m1的右侧左边界收缩到m1。每次迭代区间长度变成原来的2/3。虽然比二分的1/2收敛慢一点但换来的是对单峰函数的通用求解能力。二分和三分的关系可以这样理解二分是“利用有序性缩小范围”三分是“利用趋势性缩小范围”本质都是“每轮排除掉一定不可能的区域”只是判断依据从“大小关系”换成了“两个采样点的相对高低”。2.2 内层单峰性固定E点后F怎么找现在面临两个变量一个E一个F。先处理内层如果E固定了问题就退化成“在线段CD上找一个F使得[ \frac{|EF|}{q} \frac{|FD|}{r} ]最小”。把F用参数t表示令F C t * (D - C)t在[0,1]区间内。这个函数长什么样|EF|是F点到固定点E的距离在F沿直线移动的过程中距离随t的变化是一个“先减后增”或单调的函数本质上是二次函数开根号是凸的。|FD|是F到D点的距离随着t增大而单调减小也是一个凸函数。两个凸函数乘以正系数相加仍然是凸函数也就是单峰的。所以固定E之后g(t)在[0,1]上一定能用三分找到最小值。这里有一个关键直觉F不能简单地取“E到D连线与CD的交点”或者“E在CD上的垂足”。因为E到D直线穿过CD的交点只考虑了平地路径完全忽略了CD传送带本身的速度优势r。当r很大时你可能愿意在CD上多走一段去享受高速当r很小甚至小于q时你会尽量少在CD上走。这个“用什么速度走多远”的权衡只有三分能统一处理。2.3 外层单峰性为什么可以套两层三分内层解决了“固定E找最优F”外层就是“E选在哪里”。定义h(E) 内层三分得到的最短时间。如果h(E)关于E在线段AB上的位置也是单峰的那么外层也能用三分嵌套起来就是双层三分。严格证明h(E)的单峰性需要用到凸函数的保凸变换性质竞赛中很少要求你写严谨证明但你必须形成这样一个认知在这个模型里E越靠近A前半段传送带走得少但可能换来更短的平地连接路线E越靠近B前半段传送带走得长但可能在后续路径上绕远。两种极端都不一定最优中间必然存在一个权衡出来的最佳位置这个“先减后增”的形态就是单峰。用三分去逼近它就是顺理成章的事。外层三分时每次需要一个“E确定后的最短总时间”这个值需要再调用一次内层三分来求。于是算法的结构是外层三分枚举E的位置内层三分对每个E求最优F。复杂度是 O(迭代次数^2)迭代次数各取100次就是1e4次计算每次计算几个距离完全足够在时限内跑完。3. 双层三分完整实现公式推导与C代码3.1 目标函数怎么参数化实现第一步是把E和F都参数化。设[ E A k \times (B - A), \quad k \in [0,1] ] [ F C t \times (D - C), \quad t \in [0,1] ]这样“在线段AB上选一个点”就等价于“在区间[0,1]上选一个k”“在线段CD上选一个点”等价于“在区间[0,1]上选一个t”。参数化之后所有点坐标都能用k、t的线性函数表示距离公式也能直接代入。目标函数写出来就是[ cost(k,t) \frac{k \times |AB|}{p} \frac{|E(k) - F(t)|}{q} \frac{(1-t) \times |CD|}{r} ]其中E(k)、F(t)分别是上面的参数化点。外层三分是枚举k内层三分是枚举t。注意cost里已经包含了从A到E的路程、E到F的平地路程、F到D的路程三个部分分别除以对应速度。有个小细节值得说明k和t都在[0,1]内这就意味着三分搜索的左右边界是0和1。这个边界天然保证了搜索范围不会越出线段所以不需要额外判断点是否在线段上简化了代码。理论上k取0就是直接从A开始走k取1就是一直走到B才下传送带这两个边界都能被三分覆盖到。3.2 可直接AC的代码完整的C实现如下我用的是固定迭代次数的写法注释写清楚了每一段的作用#include bits/stdc.h using namespace std; struct Point { double x, y; }; Point A, B, C, D; double p, q, r; // 两点间距离 double dist(const Point a, const Point b) { double dx a.x - b.x; double dy a.y - b.y; return sqrt(dx * dx dy * dy); } // 在线段ab上按比例k取点k属于[0,1] Point getPoint(const Point a, const Point b, double k) { return {a.x (b.x - a.x) * k, a.y (b.y - a.y) * k}; } // 已知kE的位置求tF的位置时的总时间 double calc(double k, double t) { Point E getPoint(A, B, k); Point F getPoint(C, D, t); return dist(A, E) / p dist(E, F) / q dist(F, D) / r; } // 内层三分固定k求最优t返回最短时间 double inner(double k) { double l 0, r 1; for (int i 0; i 100; i) { double m1 l (r - l) / 3; double m2 r - (r - l) / 3; if (calc(k, m1) calc(k, m2)) r m2; else l m1; } return calc(k, (l r) / 2); } int main() { cin A.x A.y B.x B.y; cin C.x C.y D.x D.y; cin p q r; // 外层三分枚举kE在线段AB上的位置 double l 0, r 1; for (int i 0; i 100; i) { double m1 l (r - l) / 3; double m2 r - (r - l) / 3; if (inner(m1) inner(m2)) r m2; else l m1; } cout fixed setprecision(2) inner((l r) / 2) endl; return 0; }这段代码在绝大多数在线评测系统上可以直接通过输出保留两位小数。核心就是两层三分各循环100次每次循环内部调用距离计算整体次数是100 * 100 1e4次加上一些常数操作运行时间可以忽略不计。3.3 精度控制循环次数、eps和浮点陷阱很多初学者写三分时喜欢用while (r - l eps)来控制循环这种做法在这个题里容易出问题。问题出在嵌套结构上外层三分每比较一次inner(m1)和inner(m2)内部都要做一次完整的三分搜索。如果内层用eps1e-8控制外层也用eps1e-8那么内层的误差会累积到外层比较上可能导致外层判断方向错误最终答案偏差很大。我自己测试下来固定迭代次数的写法最稳。原因很简单区间[0,1]每次缩为2/3迭代100次后区间长度是(2/3)^100这个数值约为2.46e-18远远超过double的精度需求。而且100次迭代的计算量才1e4次根本不缺这点时间。如果你担心不够可以迭代150次结果也不会有任何变化。还有一个浮点陷阱是判断条件里的严格小于号。写if (calc(k, m1) calc(k, m2))时如果两次计算值非常接近理论上会出现随机方向选择但实际中因为double的精度足够对最终结果影响可以忽略。如果你实在不放心可以把小于号改成小于等于号但我在大量测试中发现两者的AC结果没有区别。最后输出时不要忘记用fixed和setprecision(2)。这个题要求保留两位小数直接用cout默认格式可能会输出科学计数法到时候你怎么查都查不出问题结果就在这翻车。4. 实战避坑边界、读入、对拍与赛场选择4.1 最容易踩的6个坑第一个坑是读入顺序。这道题的输入顺序是先给A、B两个点再给C、D两个点最后给p、q、r三个速度。如果你按习惯先读A、C、再读B、D计算就会完全错位而且样例还很可能能跑出看起来合理的结果让你很难察觉。做计算几何题第一步就是先画个图把输入变量标在图上再开始写代码。第二个坑是分不清传送带对应哪个速度。题目里AB之间是传送带速度是pCD之间是传送带速度是r平地速度是q。方向不要搞反特别是当p和r不相等时AB和CD的传送带速度是不同的。错了的话答案可能差很多但又不会报错是最隐蔽的一种错误。第三个坑是忽略线段长度为0的退化情况。有些测试数据里A和B重合或者C和D重合此时线段退化成点。虽然k和t的三分区间依然是[0,1]但取任何值都得到同一个点函数变成常数三分仍然能正确返回不过如果你在代码里额外做了“线段长度为0就除0”的操作反而会出问题。我的建议是不要做任何特判直接让三分处理它天然兼容退化情况。第四个坑是double比较用。浮点数比较相等是非常危险的操作如果你用while (r - l eps)循环那没问题但如果你在某处想判断“E是否到了B点”用if (k 1.0)这种写法基本等于随机行为。正确的做法是不比较相等或者用fabs(a - b) eps的形式。第五个坑是内层三分的返回值写错。内层三分最后返回的是calc(k, (lr)/2)不是返回t的最佳值。如果你写成return (lr)/2外层拿到的就是“最优比例”而不是“最短时间”整个外层比较就失去了意义最终答案完全错误。第六个坑是只三分了一层。有些人会想能不能先三分E然后把F直接取成某个特殊点这个在前面已经论证过不行。F和E是耦合的必须嵌套求。这类题如果只写一层三分通常只能过样例一上大数据就错。4.2 如何用暴力对拍确认三分写对了三分写完之后怎么确认它不是“碰巧对”最可靠的方式是写一个暴力枚举程序对拍。这个题的暴力特别简单把k和t都离散成1000份然后双重循环找最小值。虽然复杂度是1e6但本地跑完全没问题。对拍思路是生成随机数据分别跑暴力程序和三分程序比较输出。如果两者误差在1e-4以内说明三分逻辑基本正确。下面是暴力的核心代码可以直接拿来做对拍参考double brute() { double ans 1e18; for (int i 0; i 1000; i) { for (int j 0; j 1000; j) { double k 1.0 * i / 1000; double t 1.0 * j / 1000; ans min(ans, calc(k, t)); } } return ans; }对拍时随机生成A、B、C、D的坐标范围和速度都随机。多跑几百组数据如果三分结果和暴力结果一直很接近就可以放心提交。这里有一个经验三分如果写错了通常对拍很快就会暴露因为错误的比较方向会导致结果偏差明显很难蒙混过关。我习惯在本地写一个生成随机数据的脚本然后用shell循环跑几百次对拍。这个过程看起来麻烦但能省掉反复提交被罚时的痛苦。对拍是竞赛基本功这道题非常适合用来练习这个技能。4.3 赛场上这道题的最优时间分配如果是在正式比赛中碰到这个题我的建议是花5分钟读题立刻意识到底层逻辑是“两个变量要同时最优”然后在草稿纸上写出cost(k,t)公式。只要公式写出来剩下的就是套三层三分的模板总时间大约15分钟到20分钟。关键的一点是不要在证明“为什么单峰”上卡太久。你有直觉判断它是单峰就先用三分写出来再用暴力对拍验证。赛场上没有老师逼你写严谨证明AC才是目标。这道题你花30分钟还写不出来往往不是代码问题而是思路还停留在“找几何关系”上。当你意识到这是个数值优化问题思路就彻底打开了。还有一个小建议如果赛场允许先写一个接受题目范围但只输出暴力的程序用来兜底拿部分分。尤其是在不确定三分写法对不对的时候暴力至少能保证一些测试点有分。等三分写完并和暴力对拍通过后再提交最终版本。5. 从传送带延伸出去二分三分的适用边界5.1 二分查找模板为什么救不了这道题日常刷题用到最多的还是二分查找网上那些“二分查找模板”“二分答案技巧”刷得特别熟但真正遇到传送带这种题时模板一点都用不上。原因在于二分依赖单调性你要查找的目标必须和条件值之间有单调关系比如“最小化最大值”类问题check函数是单调的。这个题的目标函数在两条线段上都不是单调的。随着E从A往B移动总时间先变小后变大随着F从C往D移动时间也是先变小后变大。无论你怎么切割区间都无法用“中点值与目标值比较”来确定答案在哪一侧。这就是为什么你需要三分三分是“二分思想”在非单调但单峰场景下的推广。很多人学算法时容易犯一个毛病把二分查找当成一个模板来背却没理解它背后的“排除思想”。二分能排除一半三分能排除三分之一它们的共同点是“利用函数形态来缩小范围”。掌握了这个抽象层次你才能在看到传送带时想到三分而不是只会对着单调数组二分。5.2 以后刷题怎么快速判断该用哪种方法判断该用二分还是三分我总结了一套快速识别法。先问自己题目要求的答案是否随着某个变量呈现“单调变化”如果是用二分。如果答案随着变量呈现“先优后劣”或“先劣后优”的趋势也就是存在一个最佳点用三分。具体到几何题里很多“在线段上找一个点使得到某个目标的时间/距离/角度最优”的问题答案常常是单峰的都可以优先考虑三分。比如“在一条直线上选一个位置建仓库让所有人到仓库的总距离最小”如果你把位置当变量总距离函数是凸的直接三分。再比如“在河岸上选码头位置让总路径最短”本质也是三分。传送带这道题给了一个更高级的范式当题目有两个变量共同决定答案时如果两个变量都能“独立三分”就嵌套起来。外层三分一个变量内层对另一个变量做最优响应。这种“嵌套三分”在计算几何和数值优化里非常常见学会了它你就能解决一大批“看起来像几何实际上是函数优化”的题目。最后分享一个我个人的习惯。每次写完三分数值题我都会手动打印几组点的图像固定E打印F从C到D移动时时间的变化曲线确认它确实像碗一样先降后升。这个习惯帮我避免了很多次“想当然写三分其实函数不单峰”的翻车。传送带这题我当年第一次写的时候也踩过这个坑总觉得既然题解都说是三分那函数一定单峰结果自己一画图才发现对某些极端数据并不是很规整但三分依然能收敛到正确答案。后来我想明白了三分不需要函数严格凸只要它“大体单峰、没有多个差距很大的局部最优”就能用这也是它比黄金分割法更实用的原因之一。 
长河君 · 2026/10/4 7:38:02 · 阅读 1.2k 传送带问题：二分到三分的思维跃迁与嵌套三分实现
做二分三分的练习题时最怕遇到哪种题就是把模板背得滚瓜烂熟但看到题目根本不知道该往哪个方向套。SCOI2010这道“传送带”就是这个类型的典型代表。它出现在基础算法提高篇的二分与三分章节里题目本身并不长但如果你只会二分查找模板第一次看到基本都会卡住这题既没有单调数组让你查也没法直接二分答案它要的是在一个平面上找两个点让总时间最短。我当时做这道题的时候第一反应是用几何方法硬推推了半天发现情况特别多最后老老实实回去学三分才明白出题人把它放在这一章的用意。这道题的核心价值在于它用最直观的方式展示了“单峰函数为什么可以三分求解”而且是一个经典的“嵌套三分”模型。整道题没有复杂的算法结构代码量也很小但背后的思路转换非常关键。这篇文章我会把从题意拆解、单峰性论证、公式推导到最终AC代码、调试避坑完整讲一遍适合刚学完二分、准备向三分进阶的竞赛选手参考。1. 这题到底在问什么传送带模型与最优化目标1.1 题意拆解与变量定义先看原题模型。平面上有两条线段AB和CDA、B两点之间有一条传送带C、D两点之间也有一条传送带。一个人在平地上行走的速度是q在传送带AB上行走的速度是p在传送带CD上行走的速度是r。这个人要从A点出发最终到达D点他可以先在AB传送带上走一段然后下传送带在平地上走一段再上传送带CD走一段最后到达D。题目要求的是这个人应该怎么规划路径使得总时间最短。这里的路径不是随意曲线而是被约束成“三段走法”在AB上从A走到某个点E从E直线走到CD上的某个点F再从F走到D。为什么中间一定是直线因为平地上没有任何速度差异两点之间直线最短所以E到F必然走直线段。把变量说清楚E在线段AB上F在线段CD上。我们需要同时确定E的位置和F的位置使得[ T \frac{|AE|}{p} \frac{|EF|}{q} \frac{|FD|}{r} ]最小。注意三个速度的单位要一致题目给的是速度所以时间是路程除以速度。有些题目给的是“单位路程花的时间”那种情况就要反过来乘这是读题时需要分辨的细节下面避坑部分还会单独说。很多人拿到这个题会想E和F不都是直线吗直接让E到F的连线经过两个传送带之间最短连线不就行了问题在于两条传送带上的速度不同平地速度也可能不同所以“几何最短”并不等于“时间最短”。当传送带速度比平地快很多时你愿意在传送带上多走一段哪怕绕一点点路当传送带速度慢时你恨不得刚上就下。这个“权衡”本质上就是一个最优化问题而不是一个纯几何问题。1.2 为什么暴力枚举和贪心都不可行最容易想到的办法是枚举。E和F都是连续变量你不可能真的枚举所有点。退一步把每条线段均匀切成很多小段用双重循环暴力找最优误差取决于切分密度。切1000段就是10^6次计算每次还要算距离和除法精度还只能到千分之一显然不靠谱。切1e5段就是10^10次直接超时。也有人想贪心先让E取某个特殊点比如A或者B然后求F。但这条路也不通因为E的取值会影响F的最优位置两个变量耦合在一起不是独立决策。比如E在A点时最好的F可能是靠近C的E在B点时最好的F可能就变成靠近D的。你没法先定一个再推另一个。这种“两个连续变量互相影响又都要在固定范围内选值”的问题就是一个典型的“区间内找函数极值”问题。如果函数具有单调性可以二分如果函数是单峰的就可以三分。传送带这道题的精髓就在于它把单峰函数从一维常识题升级成了二维嵌套题逼迫你把三分算法真正理解透。2. 为什么非要用三分单峰函数决定了算法走向2.1 三分和二分到底差在哪二分查找能在有序数组里快速找目标值依赖的是“单调性”。你把区间一分为二根据中点和目标值的大小关系能确定答案在左半边还是右半边。但最优化问题里函数往往不是单调的而是先下降后上升或先上升后下降这种情况没有单调性可用但满足“单峰性”。三分算法就是把区间分成三段不是找中点而是找两个三分点m1和m2。比较f(m1)和f(m2)的大小就能判断峰的位置在哪一侧。以“极小值”为例假设函数先下降后上升如果f(m1)小于f(m2)说明m1更接近谷底那么谷底位于m2的左侧右边界就可以收缩到m2反过来如果f(m1)大于f(m2)说明m2更接近谷底谷底位于m1的右侧左边界收缩到m1。每次迭代区间长度变成原来的2/3。虽然比二分的1/2收敛慢一点但换来的是对单峰函数的通用求解能力。二分和三分的关系可以这样理解二分是“利用有序性缩小范围”三分是“利用趋势性缩小范围”本质都是“每轮排除掉一定不可能的区域”只是判断依据从“大小关系”换成了“两个采样点的相对高低”。2.2 内层单峰性固定E点后F怎么找现在面临两个变量一个E一个F。先处理内层如果E固定了问题就退化成“在线段CD上找一个F使得[ \frac{|EF|}{q} \frac{|FD|}{r} ]最小”。把F用参数t表示令F C t * (D - C)t在[0,1]区间内。这个函数长什么样|EF|是F点到固定点E的距离在F沿直线移动的过程中距离随t的变化是一个“先减后增”或单调的函数本质上是二次函数开根号是凸的。|FD|是F到D点的距离随着t增大而单调减小也是一个凸函数。两个凸函数乘以正系数相加仍然是凸函数也就是单峰的。所以固定E之后g(t)在[0,1]上一定能用三分找到最小值。这里有一个关键直觉F不能简单地取“E到D连线与CD的交点”或者“E在CD上的垂足”。因为E到D直线穿过CD的交点只考虑了平地路径完全忽略了CD传送带本身的速度优势r。当r很大时你可能愿意在CD上多走一段去享受高速当r很小甚至小于q时你会尽量少在CD上走。这个“用什么速度走多远”的权衡只有三分能统一处理。2.3 外层单峰性为什么可以套两层三分内层解决了“固定E找最优F”外层就是“E选在哪里”。定义h(E) 内层三分得到的最短时间。如果h(E)关于E在线段AB上的位置也是单峰的那么外层也能用三分嵌套起来就是双层三分。严格证明h(E)的单峰性需要用到凸函数的保凸变换性质竞赛中很少要求你写严谨证明但你必须形成这样一个认知在这个模型里E越靠近A前半段传送带走得少但可能换来更短的平地连接路线E越靠近B前半段传送带走得长但可能在后续路径上绕远。两种极端都不一定最优中间必然存在一个权衡出来的最佳位置这个“先减后增”的形态就是单峰。用三分去逼近它就是顺理成章的事。外层三分时每次需要一个“E确定后的最短总时间”这个值需要再调用一次内层三分来求。于是算法的结构是外层三分枚举E的位置内层三分对每个E求最优F。复杂度是 O(迭代次数^2)迭代次数各取100次就是1e4次计算每次计算几个距离完全足够在时限内跑完。3. 双层三分完整实现公式推导与C代码3.1 目标函数怎么参数化实现第一步是把E和F都参数化。设[ E A k \times (B - A), \quad k \in [0,1] ] [ F C t \times (D - C), \quad t \in [0,1] ]这样“在线段AB上选一个点”就等价于“在区间[0,1]上选一个k”“在线段CD上选一个点”等价于“在区间[0,1]上选一个t”。参数化之后所有点坐标都能用k、t的线性函数表示距离公式也能直接代入。目标函数写出来就是[ cost(k,t) \frac{k \times |AB|}{p} \frac{|E(k) - F(t)|}{q} \frac{(1-t) \times |CD|}{r} ]其中E(k)、F(t)分别是上面的参数化点。外层三分是枚举k内层三分是枚举t。注意cost里已经包含了从A到E的路程、E到F的平地路程、F到D的路程三个部分分别除以对应速度。有个小细节值得说明k和t都在[0,1]内这就意味着三分搜索的左右边界是0和1。这个边界天然保证了搜索范围不会越出线段所以不需要额外判断点是否在线段上简化了代码。理论上k取0就是直接从A开始走k取1就是一直走到B才下传送带这两个边界都能被三分覆盖到。3.2 可直接AC的代码完整的C实现如下我用的是固定迭代次数的写法注释写清楚了每一段的作用#include bits/stdc.h using namespace std; struct Point { double x, y; }; Point A, B, C, D; double p, q, r; // 两点间距离 double dist(const Point a, const Point b) { double dx a.x - b.x; double dy a.y - b.y; return sqrt(dx * dx dy * dy); } // 在线段ab上按比例k取点k属于[0,1] Point getPoint(const Point a, const Point b, double k) { return {a.x (b.x - a.x) * k, a.y (b.y - a.y) * k}; } // 已知kE的位置求tF的位置时的总时间 double calc(double k, double t) { Point E getPoint(A, B, k); Point F getPoint(C, D, t); return dist(A, E) / p dist(E, F) / q dist(F, D) / r; } // 内层三分固定k求最优t返回最短时间 double inner(double k) { double l 0, r 1; for (int i 0; i 100; i) { double m1 l (r - l) / 3; double m2 r - (r - l) / 3; if (calc(k, m1) calc(k, m2)) r m2; else l m1; } return calc(k, (l r) / 2); } int main() { cin A.x A.y B.x B.y; cin C.x C.y D.x D.y; cin p q r; // 外层三分枚举kE在线段AB上的位置 double l 0, r 1; for (int i 0; i 100; i) { double m1 l (r - l) / 3; double m2 r - (r - l) / 3; if (inner(m1) inner(m2)) r m2; else l m1; } cout fixed setprecision(2) inner((l r) / 2) endl; return 0; }这段代码在绝大多数在线评测系统上可以直接通过输出保留两位小数。核心就是两层三分各循环100次每次循环内部调用距离计算整体次数是100 * 100 1e4次加上一些常数操作运行时间可以忽略不计。3.3 精度控制循环次数、eps和浮点陷阱很多初学者写三分时喜欢用while (r - l eps)来控制循环这种做法在这个题里容易出问题。问题出在嵌套结构上外层三分每比较一次inner(m1)和inner(m2)内部都要做一次完整的三分搜索。如果内层用eps1e-8控制外层也用eps1e-8那么内层的误差会累积到外层比较上可能导致外层判断方向错误最终答案偏差很大。我自己测试下来固定迭代次数的写法最稳。原因很简单区间[0,1]每次缩为2/3迭代100次后区间长度是(2/3)^100这个数值约为2.46e-18远远超过double的精度需求。而且100次迭代的计算量才1e4次根本不缺这点时间。如果你担心不够可以迭代150次结果也不会有任何变化。还有一个浮点陷阱是判断条件里的严格小于号。写if (calc(k, m1) calc(k, m2))时如果两次计算值非常接近理论上会出现随机方向选择但实际中因为double的精度足够对最终结果影响可以忽略。如果你实在不放心可以把小于号改成小于等于号但我在大量测试中发现两者的AC结果没有区别。最后输出时不要忘记用fixed和setprecision(2)。这个题要求保留两位小数直接用cout默认格式可能会输出科学计数法到时候你怎么查都查不出问题结果就在这翻车。4. 实战避坑边界、读入、对拍与赛场选择4.1 最容易踩的6个坑第一个坑是读入顺序。这道题的输入顺序是先给A、B两个点再给C、D两个点最后给p、q、r三个速度。如果你按习惯先读A、C、再读B、D计算就会完全错位而且样例还很可能能跑出看起来合理的结果让你很难察觉。做计算几何题第一步就是先画个图把输入变量标在图上再开始写代码。第二个坑是分不清传送带对应哪个速度。题目里AB之间是传送带速度是pCD之间是传送带速度是r平地速度是q。方向不要搞反特别是当p和r不相等时AB和CD的传送带速度是不同的。错了的话答案可能差很多但又不会报错是最隐蔽的一种错误。第三个坑是忽略线段长度为0的退化情况。有些测试数据里A和B重合或者C和D重合此时线段退化成点。虽然k和t的三分区间依然是[0,1]但取任何值都得到同一个点函数变成常数三分仍然能正确返回不过如果你在代码里额外做了“线段长度为0就除0”的操作反而会出问题。我的建议是不要做任何特判直接让三分处理它天然兼容退化情况。第四个坑是double比较用。浮点数比较相等是非常危险的操作如果你用while (r - l eps)循环那没问题但如果你在某处想判断“E是否到了B点”用if (k 1.0)这种写法基本等于随机行为。正确的做法是不比较相等或者用fabs(a - b) eps的形式。第五个坑是内层三分的返回值写错。内层三分最后返回的是calc(k, (lr)/2)不是返回t的最佳值。如果你写成return (lr)/2外层拿到的就是“最优比例”而不是“最短时间”整个外层比较就失去了意义最终答案完全错误。第六个坑是只三分了一层。有些人会想能不能先三分E然后把F直接取成某个特殊点这个在前面已经论证过不行。F和E是耦合的必须嵌套求。这类题如果只写一层三分通常只能过样例一上大数据就错。4.2 如何用暴力对拍确认三分写对了三分写完之后怎么确认它不是“碰巧对”最可靠的方式是写一个暴力枚举程序对拍。这个题的暴力特别简单把k和t都离散成1000份然后双重循环找最小值。虽然复杂度是1e6但本地跑完全没问题。对拍思路是生成随机数据分别跑暴力程序和三分程序比较输出。如果两者误差在1e-4以内说明三分逻辑基本正确。下面是暴力的核心代码可以直接拿来做对拍参考double brute() { double ans 1e18; for (int i 0; i 1000; i) { for (int j 0; j 1000; j) { double k 1.0 * i / 1000; double t 1.0 * j / 1000; ans min(ans, calc(k, t)); } } return ans; }对拍时随机生成A、B、C、D的坐标范围和速度都随机。多跑几百组数据如果三分结果和暴力结果一直很接近就可以放心提交。这里有一个经验三分如果写错了通常对拍很快就会暴露因为错误的比较方向会导致结果偏差明显很难蒙混过关。我习惯在本地写一个生成随机数据的脚本然后用shell循环跑几百次对拍。这个过程看起来麻烦但能省掉反复提交被罚时的痛苦。对拍是竞赛基本功这道题非常适合用来练习这个技能。4.3 赛场上这道题的最优时间分配如果是在正式比赛中碰到这个题我的建议是花5分钟读题立刻意识到底层逻辑是“两个变量要同时最优”然后在草稿纸上写出cost(k,t)公式。只要公式写出来剩下的就是套三层三分的模板总时间大约15分钟到20分钟。关键的一点是不要在证明“为什么单峰”上卡太久。你有直觉判断它是单峰就先用三分写出来再用暴力对拍验证。赛场上没有老师逼你写严谨证明AC才是目标。这道题你花30分钟还写不出来往往不是代码问题而是思路还停留在“找几何关系”上。当你意识到这是个数值优化问题思路就彻底打开了。还有一个小建议如果赛场允许先写一个接受题目范围但只输出暴力的程序用来兜底拿部分分。尤其是在不确定三分写法对不对的时候暴力至少能保证一些测试点有分。等三分写完并和暴力对拍通过后再提交最终版本。5. 从传送带延伸出去二分三分的适用边界5.1 二分查找模板为什么救不了这道题日常刷题用到最多的还是二分查找网上那些“二分查找模板”“二分答案技巧”刷得特别熟但真正遇到传送带这种题时模板一点都用不上。原因在于二分依赖单调性你要查找的目标必须和条件值之间有单调关系比如“最小化最大值”类问题check函数是单调的。这个题的目标函数在两条线段上都不是单调的。随着E从A往B移动总时间先变小后变大随着F从C往D移动时间也是先变小后变大。无论你怎么切割区间都无法用“中点值与目标值比较”来确定答案在哪一侧。这就是为什么你需要三分三分是“二分思想”在非单调但单峰场景下的推广。很多人学算法时容易犯一个毛病把二分查找当成一个模板来背却没理解它背后的“排除思想”。二分能排除一半三分能排除三分之一它们的共同点是“利用函数形态来缩小范围”。掌握了这个抽象层次你才能在看到传送带时想到三分而不是只会对着单调数组二分。5.2 以后刷题怎么快速判断该用哪种方法判断该用二分还是三分我总结了一套快速识别法。先问自己题目要求的答案是否随着某个变量呈现“单调变化”如果是用二分。如果答案随着变量呈现“先优后劣”或“先劣后优”的趋势也就是存在一个最佳点用三分。具体到几何题里很多“在线段上找一个点使得到某个目标的时间/距离/角度最优”的问题答案常常是单峰的都可以优先考虑三分。比如“在一条直线上选一个位置建仓库让所有人到仓库的总距离最小”如果你把位置当变量总距离函数是凸的直接三分。再比如“在河岸上选码头位置让总路径最短”本质也是三分。传送带这道题给了一个更高级的范式当题目有两个变量共同决定答案时如果两个变量都能“独立三分”就嵌套起来。外层三分一个变量内层对另一个变量做最优响应。这种“嵌套三分”在计算几何和数值优化里非常常见学会了它你就能解决一大批“看起来像几何实际上是函数优化”的题目。最后分享一个我个人的习惯。每次写完三分数值题我都会手动打印几组点的图像固定E打印F从C到D移动时时间的变化曲线确认它确实像碗一样先降后升。这个习惯帮我避免了很多次“想当然写三分其实函数不单峰”的翻车。传送带这题我当年第一次写的时候也踩过这个坑总觉得既然题解都说是三分那函数一定单峰结果自己一画图才发现对某些极端数据并不是很规整但三分依然能收敛到正确答案。后来我想明白了三分不需要函数严格凸只要它“大体单峰、没有多个差距很大的局部最优”就能用这也是它比黄金分割法更实用的原因之一。