hiho一下第65周微软面试题《Highway》题目分析

因为i到达y[i]就离开了，所以j从y[i]到y[j]的时间没有车阻挡，正常行驶。

在这个过程中我们对于车j的行驶分段进行了计算：

x[j]到y[i]：车j经过这一段的时间为max(t[i], t[j])

y[i]到y[j]：车j经过这一段的时间为max(t[j])

再扩展到多个车的情况：

----c-----c-----c-----|-----|-----|---->
    k     j     i    y[i]  y[j]  y[k]

对于车k，我们需要将整个过程分为3段：

x[k]到y[i]：车k经过这一段的时间为max(t[i], t[j], t[k])

y[i]到y[j]：车k经过这一段的时间为max(t[j], t[k])

y[j]到y[k]：车k经过这一段的时间为max(t[k])

通过这两个例子我们也就得到了一个计算某个车时间的算法：

对于车j来说，需要根据y的的情况，将其从起点到终点的路程分为x[j]~y[i],...,y[i']~y[j]若干段。

同时每一段时间的时间值为:

max(t[j], t[i] | 车i需要经过这段路 且 车i在车j前面)

而该时间值是具有传递性的。比如说存在i,j,k，x[i]>x[j]>x[k]，且他们都经过同一段路，则：

对于i来说，取值为max(t[i])

对于j来说，取值为max(t[i], t[j])

对于k来说，取值为max(t[i], t[j], t[k])

若我们按照车从前往后的顺序来处理的话，我们维护一个t值：

计算i时，取t = t[i]

计算j时，取t = max(t, t[j])

计算k时，取t = max(t, t[k])

因此我们需要对每一个y[i]维护一个t值，这样就可以使得计算通过每一段路的时间变为O(1)。

综上，可以得到我们的解题伪代码：

p = y  // copy array y
sort(p)    
For x[i] from large to small
    nowPosition = x[i]
    t = 0
    For j = 1 .. n
        If p[j] > x[i] Then
            t += (p[j] - nowPosition) / v[i]
            t = max(t[j], t)
            t[j] = t;            // update t
            If p[j] == y[i] Then
                ans[i] = t
                break;
            End If
        End If
    End For
End For