题目链接P1258 小车问题 - 洛谷数学解法#includebits/stdc.h using namespace std; int main() { double s,a,b; cin s a b; double w 2*a*s/(3*ab); 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相遇ab(s−w)(1−a/b)相遇点 乙在“车送甲 折返”这两段时间里一直走到的位置wa(bs−wab(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) / (ab)。 // 相遇点 乙的位置 a * (t1 t2)。 // 第 3 段车送乙走完剩余 s - a*(t1t2)耗时 t3 (s - a*(t1t2)) / b。 // 乙总时间 t1 t2 t3。 // // 性质x 越大甲坐得越远乙越晚被接上乙完成时间越大 → 单调递增。 // 因此使乙 T0 的 x是一段前缀 [0, x_max]只需看 x0 能否满足 // 下界即可——但 x0 时甲完全没坐车甲自己可能来不及。所以真正的 // 判断要同时满足甲和乙用二者的 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; }
)
