hiho一下第65周微軟面試題《Highway》題目分析

那么這個(gè)性質(zhì)有什么用呢？

首先第一點(diǎn)：

在前面的汽車始終不受后面的汽車影響。

也就是說，最前面的一輛車一定不受任何車影響，所以x[i]最大的車一定是按自己最大速度行駛到y[i]。

然后我們?cè)诳紤]第二輛車時(shí)，因?yàn)榈谝惠v車的情況我們已經(jīng)清楚，所以第二輛車也就比較容易計(jì)算。

依次類推，我們?nèi)舭凑掌噺那巴蟮捻樞蜻M(jìn)行處理，考慮的因素會(huì)比較少一點(diǎn)。

所以我們讀入數(shù)據(jù)之后要做的第一件事是根據(jù)x[i]進(jìn)行排序。再根據(jù)x[i]從大到小進(jìn)行處理。

就算是優(yōu)化了處理順序，追及問題仍然很麻煩。對(duì)于第i輛車，我們要考慮在它離開單行道，會(huì)追上多少輛車，光是想想就覺得頭疼。

所以我們必須要考慮其他的途徑，這里我們需要用到不能超車這個(gè)條件產(chǎn)生的第二的性質(zhì)：

對(duì)于道路上任意一點(diǎn)k，兩輛車i,j，若車i在車j前，則車j經(jīng)過該點(diǎn)的時(shí)間一定大于等于車i經(jīng)過該點(diǎn)的時(shí)間。

我們舉個(gè)例子來說明：

|---c---c---|--->
    j   i   k

其結(jié)果會(huì)有3種：

車i到達(dá)k點(diǎn)時(shí)，車j仍未追上i

|---c---|c------>
    j   ki      

顯然車j還要再經(jīng)過一段時(shí)間才能到達(dá)k，那么i經(jīng)過k的時(shí)間一定小于j。

車i到達(dá)k點(diǎn)時(shí)，車j剛好追上i

|------|cc------>
       kji

顯然車j和車i同時(shí)到達(dá)k，那么i經(jīng)過k的時(shí)間等于j

車i到達(dá)k點(diǎn)前，車j就已經(jīng)追上i

|---cc------|--->
    ji      k

這種情況下，車j的最大速度顯然大于車i。但是車j不能超過車i，當(dāng)車j追上車i時(shí)，就以和車i同樣的速度前進(jìn)。那么他們通過k點(diǎn)時(shí)間一定是相同的。

三種情況下，車j經(jīng)過點(diǎn)k的時(shí)間都是大于等于車i的。

同理我們可以將這個(gè)情況擴(kuò)展：

對(duì)于多個(gè)車來說，最后一個(gè)車經(jīng)過某個(gè)點(diǎn)的時(shí)間一定大于或等于前面的車經(jīng)過該點(diǎn)時(shí)間的最大值。

得到的這個(gè)性質(zhì)又有什么用呢？我們?nèi)匀挥靡粋€(gè)例子來說明：

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

我們首先根據(jù)這個(gè)性質(zhì)，先計(jì)算出i,j分別到達(dá)y[i]的時(shí)間t[i],t[j]。

若t[j]，則表示v[j]>v[i]。但是不能夠超車，所以j到達(dá)y[i]的時(shí)間最少為t[i]。所以我們得到j到達(dá)y[i]的時(shí)間為t[i]。

因?yàn)?code style="font-family:Menlo, Monaco, Consolas, 'Courier New', monospace;font-size:12.6000003814697px;color:rgb(199,37,78);background-color:rgb(249,242,244);">i到達(dá)y[i]就離開了，所以j從y[i]到y[j]的時(shí)間沒有車阻擋，正常行駛。

在這個(gè)過程中我們對(duì)于車j的行駛分段進(jìn)行了計(jì)算：

x[j]到y[i]：車j經(jīng)過這一段的時(shí)間為max(t[i], t[j])

y[i]到y[j]：車j經(jīng)過這一段的時(shí)間為max(t[j])

再擴(kuò)展到多個(gè)車的情況：

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

對(duì)于車k，我們需要將整個(gè)過程分為3段：

x[k]到y[i]：車k經(jīng)過這一段的時(shí)間為max(t[i], t[j], t[k])

y[i]到y[j]：車k經(jīng)過這一段的時(shí)間為max(t[j], t[k])

y[j]到y[k]：車k經(jīng)過這一段的時(shí)間為max(t[k])

通過這兩個(gè)例子我們也就得到了一個(gè)計(jì)算某個(gè)車時(shí)間的算法：

對(duì)于車j來說，需要根據(jù)y的的情況，將其從起點(diǎn)到終點(diǎn)的路程分為x[j]~y[i],...,y[i']~y[j]若干段。

同時(shí)每一段時(shí)間的時(shí)間值為:

max(t[j], t[i] | 車i需要經(jīng)過這段路 且 車i在車j前面)

而該時(shí)間值是具有傳遞性的。比如說存在i,j,k，x[i]>x[j]>x[k]，且他們都經(jīng)過同一段路，則：

對(duì)于i來說，取值為max(t[i])

對(duì)于j來說，取值為max(t[i], t[j])

對(duì)于k來說，取值為max(t[i], t[j], t[k])

若我們按照車從前往后的順序來處理的話，我們維護(hù)一個(gè)t值：

計(jì)算i時(shí)，取t = t[i]

計(jì)算j時(shí)，取t = max(t, t[j])

計(jì)算k時(shí)，取t = max(t, t[k])