题意分析
给定一条单行道的高速公路,汽车都是从坐标0,向坐标无穷移动。又因为是单行道,所以后面的车无法超越前面的车。在时刻0时,有 N 辆车同时进入这条单行道,第i
辆车从坐标x[i]
进入,并且将会从坐标y[i]
处驶出(保证y[i]>x[i]
)。在行驶过程中,汽车总会保持尽可能快的速度行驶,且第i
辆车的最大速度为v[i]
。问每辆车离开高速公路的所花费的时间。
算法分析
刚拿到本题,相信最开始的想法都会是计算追及问题。然而若从这个角度去考虑的话,这题会变得非常复杂。因此我们必须要使用题目的一些特殊的性质。
根据题目的描述,该条高速公路为单行道,无法超车,我们可以有:
对于任意两辆车
i
,j
,若x[i]<x[j]
,则车i
始终在车j
之后。
那么这个性质有什么用呢?
首先第一点:
在前面的汽车始终不受后面的汽车影响。
也就是说,最前面的一辆车一定不受任何车影响,所以x[i]
最大的车一定是按自己最大速度行驶到y[i]
。
然后我们在考虑第二辆车时,因为第一辆车的情况我们已经清楚,所以第二辆车也就比较容易计算。
依次类推,我们若按照汽车从前往后的顺序进行处理,考虑的因素会比较少一点。
所以我们读入数据之后要做的第一件事是根据x[i]
进行排序。再根据x[i]
从大到小进行处理。
就算是优化了处理顺序,追及问题仍然很麻烦。对于第i辆车,我们要考虑在它离开单行道,会追上多少辆车,光是想想就觉得头疼。
所以我们必须要考虑其他的途径,这里我们需要用到不能超车这个条件产生的第二的性质:
对于道路上任意一点
k
,两辆车i
,j
,若车i
在车j
前,则车j
经过该点的时间一定大于等于车i
经过该点的时间。
我们举个例子来说明:
|---c---c---|--->
j i k
其结果会有3种:
车
i
到达k
点时,车j
仍未追上i
|---c---|c------> j ki
显然车
j
还要再经过一段时间才能到达k
,那么i
经过k
的时间一定小于j
。车
i
到达k
点时,车j
刚好追上i
|------|cc------> kji
显然车
j
和车i
同时到达k
,那么i
经过k
的时间等于j
车
i
到达k
点前,车j
就已经追上i
|---cc------|---> ji k
这种情况下,车
j
的最大速度显然大于车i
。但是车j
不能超过车i
,当车j
追上车i
时,就以和车i
同样的速度前进。那么他们通过k
点时间一定是相同的。
三种情况下,车j
经过点k的时间都是大于等于车i
的。
同理我们可以将这个情况扩展:
对于多个车来说,最后一个车经过某个点的时间一定大于或等于前面的车经过该点时间的最大值。
得到的这个性质又有什么用呢?我们仍然用一个例子来说明:
-----c-----c-----|-----|----->
j i y[i] y[j]
我们首先根据这个性质,先计算出i
,j
分别到达y[i]
的时间t[i]
,t[j]
。
若t[j]<t[i]
,则表示v[j]>v[i]
。但是不能够超车,所以j
到达y[i]
的时间最少为t[i]
。所以我们得到j
到达y[i]
的时间为t[i]
。
因为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
结果分析
本题现场只有1个人通过。该题的思维复杂度比较高,在时间很短的情况下并不容易想到正确的解题方法。
因此很多选手放弃了该题,或是利用程序骗取了一定的分数,也算是比较合理的选择。
gtdzx你好,按照您伪代码的逻辑实现未通过(已经更新nowLocation的情况下),求解答,谢谢
@van084 能否将您的实现代码贴一下。
需要加一句 nowPosition = p[j]
对,nowPosition要更新,作者可能笔误了
感觉想法没错,但是实现了w了,请问您过了吗