信奥赛数学建模：小车问题解析与C++二分法实现 1. 项目概述从“小车问题”看信奥赛中的数学建模思维最近在带学生刷信奥信息学奥林匹克的题目翻到P1258这道“小车问题”。这道题在洛谷上标注为“普及/提高”难度属于典型的数学与编程结合的题目。很多刚接触信奥的同学一看到题目描述里的小车、步行、相遇、折返头就大了感觉像是在解一道复杂的物理应用题。但实际上这道题的核心是考察选手的数学建模能力和对浮点数运算的精确控制编程实现本身并不复杂。用C来解决它正好可以锻炼我们将实际问题抽象为数学模型再用代码精确求解的完整思维链条。无论是准备普及组还是冲击提高组这类题目都是很好的试金石它能清晰地区分出只会写代码和真正会用计算机思维解决问题的人。2. 问题核心与数学模型拆解2.1 题目场景还原与变量定义我们先抛开代码把题目描述的场景用人话捋清楚。题目大意通常是甲、乙两人要从A地前往B地距离为S米。他们有一辆小车但小车只能载一人。已知人步行的速度是a小车空载或载人时的速度都是b且b a。小车可以来回行驶。问如何安排甲、乙的步行和乘车策略才能使两人同时到达B地并求出所需的总时间。这里的关键词是“同时到达”。这意味着无论过程多复杂小车来回跑最终甲和乙必须恰好在同一时刻抵达终点B。如果我们设甲先乘车乙先步行那么经典的策略是小车载着甲走到途中某个点C放下甲让其步行至B小车立即折返去接正在步行的乙然后载上乙驶向B并确保两人同时到达。设未知数S: A到B的总距离。a: 人的步行速度。b: 小车的速度。t: 目标所求的总时间。x: 甲第一次乘车到达的下车点C距离A点的距离。我们的任务就是找出x和t之间的关系并最终解出t。2.2 建立方程组与解析推导这是整个问题的核心也是思维难度所在。我们需要根据“同时到达”这一约束条件为甲和乙分别列出时间方程。对于甲先乘车后步行甲乘车从A到C距离为x速度为b耗时t1_a x / b。甲从C步行到B距离为S - x速度为a耗时t2_a (S - x) / a。甲的总时间t t1_a t2_a x/b (S - x)/a。(方程1)对于乙先步行后乘车这是难点。小车放下甲后需要折返去接乙。假设小车在点D接到乙。在小车折返接到乙之前乙一直在步行。设从出发到相遇乙步行了距离y从A点算起耗时t_walk y / a。与此同时小车放下甲后从C点折返去接乙。小车折返的路程是x - y因为相遇点D在A和C之间。小车折返的速度是b所以折返耗时t_back (x - y) / b。关键点乙开始步行的时间与小车开始折返的时间是同步的。也就是说乙步行的时间y/a应该等于甲乘车的时间x/b加上小车折返的时间(x-y)/b。即y / a x / b (x - y) / b化简这个式子y/a (x x - y) / b (2x - y) / b。 两边交叉相乘b * y a * (2x - y)by 2ax - ayby ay 2axy(a b) 2ax。 因此我们可以解出y (2a*x) / (a b)。(关系式1)接到乙之后小车载着乙从D点直接驶向B点。这段距离是S - y速度为b耗时t_ride (S - y) / b。乙的总时间t 乙步行时间 乙乘车时间 y/a (S - y)/b。(方程2)现在我们有了方程1和方程2它们都等于总时间t。因此x/b (S - x)/a y/a (S - y)/b并且我们知道了y用x表达的公式。将y (2a*x)/(ab)代入上式就可以消去y得到一个只关于x和已知量(S, a, b)的方程。理论上可以解出x再代入方程1求t。然而有一个更巧妙的思路由于甲和乙的“地位”是对称的题目并未规定谁必须先乘车最终求出的总时间t应该是一个定值。我们可以直接利用“时间相等”来推导t的公式。由方程1:t x/b (S-x)/a由方程2:t y/a (S-y)/b并且y (2a*x)/(ab)我们不直接解x而是观察整个过程。对于乙来说他步行了y乘车了S-y。他步行y的距离所花的时间y/a恰好等于小车完成“送甲”和“折返”两段路程的时间之和。这两段路程是车载甲走的x加上空车折返的(x-y)总路程是x (x-y) 2x - y车速为b所以时间也是(2x-y)/b。之前我们已经推导出y/a (2x-y)/b。从这个等式y/a (2x-y)/b出发进行变形b*y a*(2x-y)b*y 2a*x - a*yb*y a*y 2a*xy*(ab) 2a*xx y*(ab)/(2a)。(关系式2)现在把关系式2代入方程1t [y*(ab)/(2a)] / b (S - [y*(ab)/(2a)]) / a y*(ab)/(2a*b) S/a - y*(ab)/(2a*a) S/a y*(ab)/(2a) * (1/b - 1/a) S/a y*(ab)/(2a) * ((a-b)/(ab)) S/a - y*(ab)*(b-a)/(2a*a*b)... 这个形式比较复杂。更简洁的方法是我们利用两个时间方程相等x/b (S-x)/a y/a (S-y)/b将包含S的项移到一边x/b - x/a y/a - y/bx*(1/b - 1/a) y*(1/a - 1/b)x*(a - b)/(ab) y*(b - a)/(ab)x*(a-b) y*(b-a)x*(a-b) -y*(a-b)假设a ! b两边同时除以(a-b)得到x -y这显然不符合物理意义距离为正数。这说明我们直接移项化简时必须非常小心符号。正确的推导应该回到方程相等的本质。一个被广泛验证的正确公式是这类“小车接人”问题的最优解总时间公式为t S / a * (2.0 / (1 a/b))但这个公式需要理解其含义。我们可以采用一种更直观、在编程中更常用的方法二分法。2.3 二分查找法思路我们不需要显式地解出复杂的方程。既然总时间t是唯一的我们可以直接二分搜索这个时间。为什么可以二分因为对于任意一个假设的总时间T我们可以判断在这个时间内两人能否同时到达B点。判断逻辑如下假设总时间为T。计算甲的策略甲先乘车一段时间t1再步行剩余时间。设甲乘车时间为t1则乘车距离为b * t1。他需要在时间T内走完S所以有b * t1 a * (T - t1) S这个不等式表示甲即使全程最快的方式先全速乘车再步行所能走的最大距离必须至少为S他才有可能在时间T内到达。由此可以解出甲所需的最短乘车时间t1_min。 实际上更简单的判断是甲全程步行需要时间S/a如果T S/a那他无论如何也到不了。如果T S/a那么总存在一种乘车步行的组合让他刚好在T时刻到达。我们可以计算出甲需要乘车走多远。 设甲乘车距离为x则x/b (S-x)/a T。解这个方程x*(1/b - 1/a) T - S/ax*(a - b)/(a*b) T - S/ax (T - S/a) * (a*b) / (a - b)注意a - b 0所以x会是正数因为T - S/a通常也为负负负得正。这个x就是甲在T时间内到达终点所需要的最短乘车距离。关键来了甲乘车到达x处下车时用了时间t_car_to_x x / b。此时小车立即折返。在这段时间t_car_to_x内乙一直在步行走了距离y_b a * t_car_to_x。此时小车在x处乙在y_b处两者相距dist x - y_b。小车以速度b折返乙以速度a相向而行他们的相对速度是a b。因此相遇所需时间t_meet dist / (a b)。相遇时总用时为t_car_to_x t_meet。相遇后小车载上乙驶向终点B。剩余距离为S - (y_b a * t_meet)即乙相遇时的位置到B的距离。驶向终点所需时间t_final [S - (y_b a * t_meet)] / b。乙的总时间为t_car_to_x t_meet t_final。判断如果abs(乙的总时间 - T) 一个很小的精度值如1e-7并且乙的总时间 T那么我们就认为在时间T内是可行的。由于计算是连续的我们可以通过二分法不断调整T找到那个使两人时间尽可能相等且都能到达的精确值。这个二分法的判断函数check(T)返回true或false表示时间T是否可行即乙能否在T时间内到达。由于更长的T总是更容易满足条件车可以等人所以这个问题具有单调性如果时间T可行那么所有大于T的时间也都可行。这完美符合二分搜索的应用条件。注意这里有一个非常重要的细节。在判断函数中我们根据甲的行程精确计算了x乘车距离然后推演乙的行程。最终判断乙的时间是否不超过T。另一种等价的思路是根据T直接计算出两人应该的乘车距离比例但二分法更通用不易出错尤其适合编程实现。3. C代码实现与逐行解析理解了二分法模型代码实现就变得清晰了。我们将整个逻辑封装成一个check函数然后在主函数中对总时间t进行二分查找。#include iostream #include iomanip #include cmath using namespace std; double S, a, b; // 判断函数给定总时间T判断能否使两人同时到达 bool check(double T) { // 1. 计算甲在时间T内到达终点所需的乘车距离x // 公式来自x/b (S-x)/a T // 解得x (a*T - S) * b / (a - b) 注意推导过程 // 更稳妥的推导x/b S/a - x/a T x*(1/b - 1/a) T - S/a // x * (a - b) / (a*b) T - S/a // x (T - S/a) * (a*b) / (a - b) // 因为a b, 所以分母(a-b)为负。要保证x为正需要(T - S/a)也为负即T S/a。 // 但T是我们搜索的目标时间理论上会略大于S/a这里需要仔细分析。 // 实际上甲全程步行时间t_walk_all S/a全程乘车时间t_car_all S/b。 // 最优总时间T一定介于两者之间S/b T S/a。 // 所以 (T - S/a) 0 (a-b) 0 乘积为正x为正数。 double x (T - S / a) * (a * b) / (a - b); // 2. 甲乘车到x处所用时间 double t_car_to_x x / b; // 3. 在t_car_to_x时间内乙步行的距离 double y_b a * t_car_to_x; // 4. 小车折返与乙相遇所需时间 // 此时小车在x乙在y_b相距 (x - y_b)相对速度 (a b) double t_meet (x - y_b) / (a b); // 5. 相遇时乙的位置从A点算起的距离 double meet_point y_b a * t_meet; // 6. 相遇后车载乙到终点所需时间 double t_final (S - meet_point) / b; // 7. 乙的总时间 double time_b t_car_to_x t_meet t_final; // 8. 判断乙的总时间是否不超过T考虑浮点精度 // 由于计算可能存在微小误差我们允许一个极小的容差 return time_b T 1e-8; // 如果乙的时间小于等于T则T可行 } int main() { cin S a b; // 二分查找的边界最短时间是两人都全程乘车但车要跑更远最长时间是两人都全程步行。 // 更精确的下界车需要跑的距离至少是S只送一个人但实际车跑了更多路。 // 一个简单的下界是 S/b最快可能时间上界是 S/a最慢可能时间。 double left S / b; // 理论最小时间 double right S / a; // 理论最大时间 // 二分搜索直到精度满足要求 while (right - left 1e-8) { // 通常1e-7或1e-8的精度足够 double mid (left right) / 2; if (check(mid)) { // 如果时间mid可行说明可能可以更短尝试缩小右边界 right mid; } else { // 如果时间mid不可行说明需要更长时间增大左边界 left mid; } } // 输出结果保留6位小数根据题目要求调整 cout fixed setprecision(6) left endl; // 此时left和right非常接近取left或(rightleft)/2均可 return 0; }代码关键点解析精度控制这是浮点数二分的核心。循环条件while (right - left 1e-8)确保了结果至少有7位小数的精度。题目通常要求输出6位小数所以1e-8的精度是安全且足够的。判断函数逻辑check(mid)函数是整个算法的灵魂。它模拟了在给定总时间T下的策略执行过程并判断其可行性。返回true意味着时间T足够甚至可能有多余false则意味着时间不够。二分边界更新这是容易出错的地方。如果check(mid)返回true说明mid这个时间点可以完成目标。由于我们要找的是最短时间所以可能存在比mid更短的时间也可行因此我们将搜索区间的右边界right设为mid在更小的区间[left, mid]内继续搜索。反之如果返回false则说明mid时间不够必须增加时间所以将左边界left设为mid。浮点数输出使用fixed setprecision(6)来固定小数位数输出这是信奥题目的常见要求。4. 数学直接解法的探讨与对比虽然二分法通用且易于理解但“小车问题”其实存在一个优美的数学解析解。我们可以通过联立方程直接推导出总时间t。让我们回到之前的方程。设甲乘车距离为x总时间为t。 对于甲t x/b (S - x)/at S/a x*(1/b - 1/a)。(1)对于乙需要用到相遇点y。乙的总时间也是t。 乙的时间由三段组成步行到相遇点y的时间y/a加上小车从放下甲到接到乙的折返相遇时间(x-y)/b这段时间乙在步行但计算总时间时从乙的视角从出发到被接上总耗时就是y/a因为他是从0时刻开始步行的再加上从相遇点到终点的乘车时间(S-y)/b。注意这里容易混淆。更严谨地说从乙出发到被接上所用的时间就是小车从A到C再折返到相遇点D的总时间这个时间等于x/b (x-y)/b (2x-y)/b。而我们之前推导出y/a (2x-y)/b。所以乙从出发到被接上的时间既等于y/a也等于(2x-y)/b。 那么乙的总时间t y/a (S-y)/b。(2)由(1)和(2)相等S/a x*(1/b - 1/a) y/a (S-y)/b移项x*(1/b - 1/a) - y/a y/b S/b - S/ax*(a - b)/(ab) - y*(b - a)/(ab) (a - b)S/(ab)(a-b)/(ab) * (x y) (a-b)S/(ab)假设a ! b两边同时除以(a-b)/(ab)x y S。(一个重要关系)这个关系非常美妙甲乘车的距离x加上乙在相遇前步行的距离y正好等于总路程S。现在我们还有关系式y (2a*x) / (a b)。 代入x y Sx (2a*x)/(ab) Sx * [1 2a/(ab)] Sx * [(ab 2a)/(ab)] Sx * (3a b) / (ab) S所以x S * (ab) / (3a b)。然后我们将x代入甲的时间方程(1)t x/b (S-x)/a [S(ab)/(3ab)] / b [S - S(ab)/(3ab)] / a S(ab) / [b(3ab)] S[1 - (ab)/(3ab)] / a S(ab) / [b(3ab)] S[(3ab - a - b)/(3ab)] / a S(ab) / [b(3ab)] S[(2a)/(3ab)] / a S(ab) / [b(3ab)] S(2a) / [a(3ab)] S(ab) / [b(3ab)] 2S / (3ab) [S(ab) 2Sb] / [b(3ab)] S(ab 2b) / [b(3ab)] S(a 3b) / [b(3ab)]因此总时间的解析解为t S * (a 3b) / (b * (3a b))我们可以写一个更简短的C程序来验证#include iostream #include iomanip using namespace std; int main() { double S, a, b; cin S a b; double t S * (a 3*b) / (b * (3*a b)); cout fixed setprecision(6) t endl; return 0; }这个公式比二分法简洁得多运行效率也更高O(1)复杂度。在竞赛中如果能够推导并验证这个公式直接使用它是最佳选择。实操心得面对信奥中的数学题第一步应该是尝试寻找数学解析解。这不仅能锻炼数学能力还能得到最优的算法。二分法是通用性强、思维负担小的保底方法。在考场上如果时间紧张或推导受阻果断采用二分法是稳妥的策略。但平时练习时一定要深挖背后的数学原理。5. 常见错误与调试技巧在实现这道题时初学者容易遇到以下几个问题5.1 浮点数精度处理不当这是最大的坑。常见错误包括比较使用永远不要用if (a b)来比较两个浮点数。应该使用fabs(a - b) eps其中eps是一个很小的数如1e-8。二分精度设置过低或过高精度eps设置太大如1e-5可能导致结果不符合题目要求的小数位数。设置太小如1e-12可能因为浮点数误差导致无限循环或判断失误。对于要求输出6位小数的题目eps设为1e-8或1e-9是安全的选择。输出格式错误忘记使用fixed setprecision()导致输出可能是科学计数法或小数位数不对。调试技巧在二分循环中可以增加调试输出打印left,right,mid和check(mid)的值观察收敛过程。// 调试用 int iter 0; while (right - left 1e-8) { double mid (left right) / 2; bool ok check(mid); // cout Iter iter : mid mid check ok endl; if (ok) { right mid; } else { left mid; } }5.2 二分查找边界条件错误初始边界设定错误下界left必须小于等于真实解上界right必须大于等于真实解。对于本题S/b全程乘车时间是绝对的下界因为即使车不停也需要这个时间。S/a全程步行时间是绝对的上界。确保初始区间[left, right]包含真实解。更新条件写反如果check(mid)为真说明mid可行我们要找最小时间所以应该去左半区间[left, mid]搜索即right mid。反之left mid。这里写反会导致找不到解或找到错误解。记忆口诀“求最小真左移”check(mid)为真时右边界左移“求最大真右移”。5.3 数学模型理解偏差忽略“同时到达”条件只计算了一个人的时间或者错误地认为两人独立行动。对相遇过程建模错误错误计算小车折返与乙相遇的时间或位置。务必画出示意图明确每个时间段内车和人的位置、速度和方向。在解析解中代错公式如果使用数学公式一定要反复验证推导过程。可以用几组简单的数据例如S100, a1, b2手动计算再与程序输出对比。5.4 输入输出与数据类型使用float而非double在信奥中除非特别说明否则浮点数一律使用double其精度远高于float。未处理多组输入题目可能包含多组测试数据。虽然P1258通常是单组但养成好习惯使用while(cin S a b)来读取直到文件结束。一份鲁棒的代码模板#include bits/stdc.h // 竞赛常用包含大多数标准库 using namespace std; int main() { double S, a, b; // 处理多组输入的写法 while (scanf(“%lf%lf%lf”, S, a, b) ! EOF) { double t S * (a 3*b) / (b * (3*a b)); printf(“%.6lf\n”, t); // C风格输出有时比cout更快 } return 0; }6. 算法扩展与思维提升P1258小车问题是一个经典的“接送问题”或“旅行者问题”的简化版。掌握它有助于解决更复杂的问题多人接送问题如果有N个人一辆车如何安排这时二分法依然有效但判断函数check(T)会更复杂需要计算每个人在时间T内所需的乘车距离并验证小车能否按顺序完成所有接送。速度不同如果车载人和空载速度不同数学模型需要调整但二分法的框架依然适用。转化为纯数学问题这道题本质是求一个函数的最小值。设甲乘车距离为x总时间t可以表示为x的函数t(x) max( f(x), g(x) )其中f(x)是甲的时间g(x)是乙的时间。最优解发生在f(x) g(x)时。这引导我们学习“最大值最小化”的优化思想。对于信奥学习的建议刷题在精不在多像P1258这样的题目彻底弄懂其数学原理和多种解法解析解、二分法比盲目刷10道简单题更有价值。养成画图习惯对于任何涉及距离、速度、时间的题目在草稿纸上画出时间-距离图是理清关系的最有效手段。验证极端情况编写代码后用极端数据测试如a和b非常接近、S很大等情况检查程序的正确性和稳定性。对比不同方法尝试用解析解和二分法分别实现并验证结果是否一致。这能加深对问题本质的理解。最后无论是普及组还是提高组的选手这类融合了数学建模和编程实现的题目正是信息学竞赛的魅力所在。它考验的不是单纯的编码能力而是将现实问题抽象化、逻辑化和计算化的综合思维能力。把这道题吃透下次再遇到“船运货物”、“飞机调度”这类问题你就能一眼看穿它们不过是换了层外衣的“小车问题”。