本题的关键是明确这样一个概念：任何一辆车的行驶历程，初始速度是它本身的速度，之后的速度如果有变化，那么只可能越来越慢（没有任何理由会让一辆车加速）。第一次变慢的原因就是因为它和前面的车相撞，速度被降下来。注意，此时的速度不一定是前车的原始速度，而是前车在碰撞时刻的速度，因为前车在之前可能也经历了一些碰撞。而第一次相撞之后，它的速度就完全和前面那辆车一样了。
我们给每一辆车建立“速度-时间”曲线。这个曲线一定是分段阶跃函数，每一次阶跃点代表着碰撞的时刻。所以这个曲线可以用若干个{tk,vk}来表示，即tk时刻之后该车的速度变成了vk，这样在t-v曲线上就有表现为若干段柱状。这些bar围成的面积就是代表这辆车随着时间的推移，所行驶的距离。
对于第0辆车（最前面的车），它的曲线就是{0, v0}。在图像上就是从(0,v0)开始的一条横向直线。
对于第1辆车，如果它会与0号车相撞的话，它的曲线就是{0, v1}, {t1, v0}. 也就是在某一个时刻t之后，它的速度就变成了前车的速度v0。这个相撞时刻t1在此时并不难求。在图像上，1号车的曲线行程了两块bar（第二块bar是无限向右延申的）
对于第2辆车，如果它会与1号车相撞的话，我们需要计算它具体的相撞时间t2。注意这个t2的时刻可能是在t1之前，那样的话，2号车的曲线就是{0,v2},{t2,v1},{t1,v0}；也有可能t2的时刻在t1之后，那么2号车的曲线局势{0,v2},{t2,v0}.
所以对于第i辆车的曲线，它基本上是继承了第i-1辆车的曲线，区别有两处：1. 它的第一段横线开始于它的原始速度{0,vi}。 2. 第一段横线一致延伸到了与前车的相撞时刻ti。注意：ti之后的曲线完全与前车在ti之后的曲线相同。
我们现在假设这个ti已知。从出发时刻到ti，第i号车行使的距离就是x = ti*vi。相同时间内第i-1号车行驶的距离y是可以从它的曲线里读出来的：就只要数一下ti时间内包含了几块bar以及它覆盖的面积（注意可能最后包含了某块bar的一部分）。如果两车相遇，那么一定要满足x - y = gap，即两车的初始间隔。于是，我们可以根据这个条件反推ti。
举个例子。假设第i-1辆车的曲线是{0,v0},{t1,v1},{t2,v2},{t3,v3} .... 我们就挨个查看i号车与i-1号车相撞时间的时间ti是在{0,t1,t2,t3...}的那个区间里。即查看是否
t1*vi >= gap + v0*(t1-0)
如果不满足，说明在t1之前都没有追上，那么就查看
t2*vi >= gap + v0*(t1-0) + v1*(t2-t1)
如果还不满足，说明在t2之前都没有追上，那么就查看
t3*vi >= gap + v0*(t1-0) + v1*(t2-t1) + v2*(t3-t2)
假设满足了，那么说明碰撞时刻就在t2和t3之间。那么具体的时刻，就等于考察这段区间内的追及问题。在这个区间内，两辆车都是匀速运动，所以需要花费的追及时间是：
dt = [ gap + v0*(t1-0) + v1*(t2-t1) - t2*vi ] / (vi - v2)
也就是说在t2再过了dt之后，这两辆车相遇了，相撞之后速度都变成了v2（此时前车的速度）。于是我们就马上得到了第i号车的曲线：{0,vi},{t2+dt,v2},{t3,v3}... 这个曲线就是在第i-1辆车的曲线基础上，弹出若干个前端的区间，依次push_front两个新区间。
时间复杂度：我们每处理一辆车，就修改部分的曲线区间。其实每一个区间其实对应的是一个撞车事件。因为总共只会有n个撞车事件，所以整体的时间复杂度就是o(N). 这里我用了deque来方便对于前端区间的弹出、加入操作，但是本质上可以看出就等效于使用了一个栈。