D - Walker
小评
赛后补题。赛时很容易的想到了二分，但是尴尬的点在于我们想的是对时间进行二分，然后分类讨论两个人的位置关系，这就导致代码很长，而且一直存在错误没有找到。
总体来说这是一道偏简单的题目，想到了正解之后代码极其精炼，且没有多少细节，能够很轻易的解决。
题意
长度为 \(N\) 的数轴上有两个人分别位于 \(x、y\) ，两个人的步行速度分别为 \(v_x、v_y\) ，在任何时刻他们都能转换方向，求解他们走遍整根数轴需要的最短时间。
思路
由于赛时主要是我在写，所以我补这道题将从赛时思路进行转换。
赛时思路（复杂，且有错）
设 \(A\) 为左边那个人，\(B\) 为右边那个人。
二分时间，对所有的情况进行讨论：\(A\) 向左、向右，\(B\) 向左、向右。
以 \(A\) 向左进行举例，有以下几种状态：
- \(A\) 向左跑，并停在 \(0、x\) 中间：此时 \(B\) 需要跑完全程；
- \(A\) 向左跑到 \(0\) ，并停在 \(0、x\) 中间：此时 \(B\) 最左到 \(x\) ，最右到 \(N\) ；
- \(A\) 向左跑到 \(0\) ，并停在 \(x、y\) 中间：此时 \(B\) 最左到 \(A\) ，最右到 \(N\) ；
- \(A\) 向左跑到 \(0\) ，并停在 \(y、N\) 中间：此时 \(B\) 要停止在 \(N\) ；
- \(A\) 向左跑到 \(0\) 、再向右跑到 \(N\) 后停止：此时 \(B\) 不需要移动。
再以 \(A\) 向右进行举例：
- \(A\) 向右跑，并停在 \(x、N\) 中间：此时 \(B\) 需要跑完全程；
- \(A\) 向右跑到 \(N\) ，并停在 \(0、N\) 的中间：此时 \(B\) 要停止在 \(0\) ；
- \(A\) 向右跑到 \(N\) 、再向左跑到 \(0\) 后停止：此时 \(B\) 不需要移动。
可见，该方法非常复杂，但是理论能解。
正解
设 \(A\) 为左边那个人，\(B\) 为右边那个人。
两个人有如下几种方式走遍整根数轴：
- \(A\) 或者 \(B\) 一个人跑完；
- \(A、B\) 向着对方的方向一直走，直到边界；
- \(A、B\) 最终在中间的某一个点碰到（且这个位置一定在 \(x、y\) 之间）。
以上前两种情况可以直接得解，最后一种情况可以通过二分碰到的位置得解。
我的思路到这个思路有一些需要转换的地方，如下：
- 我思路II的第二种情况相当于正解的第二种情况；
- 我思路I的第二种情况相当于正解的第三种情况，碰到的位置在 \(x\) ；
- 我思路I的第四种情况相当于正解的第三种情况，碰到的位置在 \(y\) 。
AC代码
点击查看代码
double n, x, vx, y, vy;
double clac(double n, double x, double v) {
return min((n + x) / v, (n + n - x) / v); //分别计算x向左、向右跑需要的时间
}
void Solve() {
cin >> n >> x >> vx >> y >> vy;
if (x > y) swap(x, y), swap(vx, vy);
double ans = min(clac(n, x, vx), clac(n, y, vy)); //分别计算A, B跑完全程需要的时间
ans = min(ans, max((n - x) / vx, y / vy)); //分别计算A, B对穿需要的时间
double l = x, r = y, ansl = INF, ansr;
for (int i = 1; i <= 100; ++ i) {
double mid = (l + r) / 2;
ansl = clac(mid, x, vx);
ansr = clac(n - mid, y - mid, vy);
// _(mid, ansl, ansr);
if (ansl < ansr) l = mid;
else r = mid;
}
cout << min(ans, max(ansl, ansr)) << endl;
}