autoxbc
2019-03-26 23:26:54 +08:00
这个从红绿灯得到的灵感，那么应该遵守红绿灯的规则
1. 红绿灯周期为 2t (变绿 => 变红 => 变绿)
2. 绿灯可过，中间变灯可继续通过
3. 行人通过时间为 x，按照常识 x < t
单个红绿灯
绿灯半周期 t，等待时间为 0
红灯半周期，等待时间从 0 ~ t
整个周期的等待时间期望为 4/t
两个连续的随机红绿灯等待时间期望
( 4/t ) * 2 = t/2
正方形的十字路口
因为总有一边为绿灯，第一个灯的等待总是 0，则总等待就是第二个灯的等待
进入路口为绿灯开头：等待时间 t - x
进入路口为绿灯中间某点，过第一灯刚好切信号，等待时间 0
进入路口为绿灯末尾：等待时间 0
这是个线性下降曲线，期望为曲线围出的三角形在 t 上的均值
( t - x )^2/(2t)
这是个抛物线，在 y 轴有 t/2 截距，顶点在 x 轴 ( t , 0 )，开口朝上，左半边取值有效 (因为 x < t )
由此可知，当行人通过时间等于半周期时 ( x = t )，等待期望为 0，由于等待不能为负值，所以等待必为 0
因为截距为 t/2，故斜穿十字路口(4 个信号正交的信号灯)，永远比通过两个连续的随机信号灯要快，即行人因为多了一组路径，人为选择后必然节省时间
注意到单个灯的期望为 t/4，则回到题目，方案 1 & 2 的期望需要由 x 和 t 的关系算得
令 ( t - x )^2/(2t) = t/4，解出临界点为 x = ( 1 - 1/√2)t ≈ 0.2929t
当行人速度很快，x < 0.2929t 时，方案 1 更优
当行人速度较慢，x > 0.2929t 时，方案 2 更优
作为特例，当 x 接近 t 时，等待时间为 0