P1258 小车问题

题目链接：

P1258 小车问题 - 洛谷

数学解法：

#include<bits/stdc++.h> using namespace std; int main() { double s,a,b; cin >> s >> a >> b; double w = 2*a*s/(3*a+b); double t = w/a + (s-w)/b; printf("%.6lf",t); return 0; }

可以凭感觉：甲乙是要同时到达的 为什么？

假设最优方案里甲先到、乙后到，总时间由乙决定（是T乙）。

那甲“先到”这段空窗就是浪费——甲完全可以少坐一点车、多走一点路（把自己的一部分车程让给乙），自己晚一点到、乙早一点到，总时间max(T甲, T乙)只会缩短，不会变长。

然后思考怎么列方程：

已知他俩是同一时间到，路程也应该是对称的

以他们行走的路程为等式：

乙要走到w处，是要花时间的。车送甲到s−w的那一瞬间，乙根本没到w，乙才走到：

a⋅bs−w​

所以那一瞬间，车和乙的间距是：

(s−w)−a⋅bs−w​=(s−w)(1−ba​)

t相遇​=a+b(s−w)(1−a/b)​

相遇点 = 乙在“车送甲 + 折返”这两段时间里，一直走到的位置：

w=a(bs−w​+a+b(s−w)(1−a/b)​)

二分解法：

#include <bits/stdc++.h> using namespace std; // P1258 小车问题 —— 二分答案版本 // 思路：不直接求 T 的公式，而是"猜一个时间 T0，判断能不能在 T0 内完成"， // 然后在 [0, 上界] 上二分逼近最短时间。 // // 关键理解：给定 T0，判断"能不能完成"等价于—— // 是否存在一个"甲的下车点 x"，使得乙也能在 T0 内到达。 // 而甲先坐车、乙后坐车，乙是"劣势方"，所以只要乙能按时到，甲一定也能。 // 于是判断 = "是否存在 x，使乙的完成时间 <= T0"。 // 乙的完成时间，作为甲下车点 x 的函数： // 第 1 段：车送甲到 x，耗时 t1 = x / b。此期间乙步行，走了 a * t1。 // 第 2 段：车从 x 折返，乙从 a*t1 向前，相向，耗时 t2 = (x - a*t1) / (a+b)。 // 相遇点 = 乙的位置 = a * (t1 + t2)。 // 第 3 段：车送乙走完剩余 s - a*(t1+t2)，耗时 t3 = (s - a*(t1+t2)) / b。 // 乙总时间 = t1 + t2 + t3。 // // 性质：x 越大（甲坐得越远），乙越晚被接上，乙完成时间越大 → 单调递增。 // 因此"使乙 <= T0 的 x"是一段前缀 [0, x_max]，只需看 x=0 能否满足 // 下界即可——但 x=0 时甲完全没坐车，甲自己可能来不及。所以真正的 // 判断要"同时满足甲和乙"，用二者的 max。 double a, b, s; // 给定甲下车点 x，返回"两人中较晚到达者的时间"（甲步行到终点 vs 乙坐车到终点） double finish_time(double x) { // 甲：坐车到 x，然后步行 s-x double t_a = x / b + (s - x) / a; // 乙：三段（步行到相遇点 + 坐车到终点） double t1 = x / b; // 车送甲 double meet = a * t1; // 车折返时乙的位置（乙一路步行） double t2 = (x - meet) / (a + b); // 相向而行直到相遇 double meet_pt = a * (t1 + t2); // 相遇点 double t_b = (t1 + t2) + (s - meet_pt) / b; // 相遇后再坐车到终点 return max(t_a, t_b); } // 判断：能否在 T0 时间内完成 // 因为 finish_time(x) 是"下凸"的（先降后升），存在一个最优 x 使两人同时到达。 // 我们在 [0, s] 上三分（或直接取对称点）找这个最优 x 的最短时间，再和 T0 比。 bool can(double T0) { // 三分搜索最优下车点 x，使 finish_time 最小 double lo = 0, hi = s; for (int iter = 0; iter < 100; iter++) { // 100 次三分足够精确 double m1 = lo + (hi - lo) / 3; double m2 = hi - (hi - lo) / 3; if (finish_time(m1) < finish_time(m2)) hi = m2; // 最小值在左半，缩右边界 else lo = m1; // 最小值在右半，缩左边界 } double best = finish_time((lo + hi) / 2); // 最优方案的最短时间 return best <= T0; // 能不能在 T0 内完成 } int main() { cin >> s >> a >> b; // 二分上界：全步行 s/a 一定够（车只会更快，最差不用车） double lo = 0, hi = s / a; for (int iter = 0; iter < 100; iter++) { // 二分到 1e-9 级别精度 double mid = (lo + hi) / 2; if (can(mid)) hi = mid; // mid 能完成 → 尝试更小 else lo = mid; // 不能 → 尝试更大 } printf("%.6f\n", (lo + hi) / 2); return 0; }