現(xiàn)場(chǎng)沒(méi)開(kāi)，按主辦方說(shuō)法是銅牌題莫名其妙變成金牌題，深感自己化式子能力不足

補(bǔ)題鏈接：https://acm.hdu.edu.cn/showproblem.php?pid=6941

題目大意：車車（視為點(diǎn)）在一條長(zhǎng)為L(zhǎng)的長(zhǎng)直公路上行駛，一開(kāi)始沒(méi)有任何測(cè)速點(diǎn)，規(guī)定從起點(diǎn)起步時(shí)速度為0，到達(dá)終點(diǎn)時(shí)速度必須為0，車車的加速度絕對(duì)值不能超過(guò)A，接下來(lái)有N個(gè)測(cè)速點(diǎn)依次建立：

• 每個(gè)測(cè)速點(diǎn)以(S, V)的二元組整數(shù)形式給出，表示測(cè)速點(diǎn)建立在離起點(diǎn)S處，限速為V

• 車車通過(guò)每個(gè)測(cè)速點(diǎn)時(shí)不得超過(guò)測(cè)速點(diǎn)規(guī)定的速度

對(duì)于每個(gè)測(cè)速點(diǎn)的建立，您需要回答建成后會(huì)不會(huì)影響車車從起點(diǎn)到終點(diǎn)的消耗的最短時(shí)間。影響輸出1，否則輸出0

官方題解：

因?yàn)檫^(guò)于簡(jiǎn)略，自己補(bǔ)題的時(shí)候踩了很多坑……

先證明一下題解給的結(jié)論，由于我不會(huì)化式子，這里采用畫(huà)圖證明。

考慮在兩個(gè)測(cè)速點(diǎn)之間行駛，不失一般性，設(shè)v1為離起點(diǎn)更近的測(cè)速點(diǎn)的限速，令v1>v2，如果飚滿A的加速度，v-t圖大概長(zhǎng)這樣：

其中分界點(diǎn)兩側(cè)直線關(guān)于分界點(diǎn)到x軸的投影線對(duì)稱，由v-t圖的性質(zhì)我們知道圖下黑色部分的面積就是兩個(gè)測(cè)速點(diǎn)之間的距離。由于測(cè)速點(diǎn)距離一定，每個(gè)合法方案這樣畫(huà)出來(lái)的投影面積必須等于當(dāng)前黑塊的面積。我們將兩個(gè)測(cè)速點(diǎn)連線作三角形(v1, v2, 分界點(diǎn))的底，黑色部分被分為一個(gè)梯形和這個(gè)三角形。

在分界點(diǎn)上作關(guān)于直線(v1, v2)的投影，我們得到了這個(gè)三角形的高?，F(xiàn)在我們考慮改變直線(v1, 分界點(diǎn))的斜率，在前半段加速階段不違反速度限制的題設(shè)下，如圖

為了方便我們?nèi)钥紤]勻速直線運(yùn)動(dòng)，畫(huà)出藍(lán)線后分析一下這個(gè)圖的意義：如果我們另前半段加速度減緩，后半段減速的加速度變快的話，可以作出這樣一個(gè)距離與黑色部分面積一致的行駛方案，但是注意后半段因?yàn)榧铀俣冉^對(duì)值已經(jīng)超過(guò)上限，所以這樣一個(gè)方案是不可行的，為了讓時(shí)間消耗變小我們只能讓后半段的勻減速階段盡可能靠近上限A，這樣為了構(gòu)造一個(gè)距離（面積）等于三角形(v1, v2, 分界點(diǎn))的三角形，只能如圖所示做一個(gè)第3頂點(diǎn)不與平移至分界點(diǎn)的底線相交的三角形：

然后你發(fā)現(xiàn)此時(shí)藍(lán)線的末端在x坐標(biāo)上已經(jīng)超過(guò)v2點(diǎn)，即這種方案耗時(shí)更久。

對(duì)于非勻加速直線運(yùn)動(dòng)的畫(huà)法，作圖發(fā)現(xiàn)為了讓其面積滿足需求，必須有一塊面積補(bǔ)充其前期因?yàn)榈陀诜纸琰c(diǎn)產(chǎn)生的代價(jià)，使得右端點(diǎn)x坐標(biāo)大于v2點(diǎn)：

想要讓時(shí)間更短的話就只能把這些多的面積盡可能往前面堆，而堆到極限就是我們最初畫(huà)出來(lái)兩側(cè)直線對(duì)稱的方案。于是結(jié)論證畢。

現(xiàn)在開(kāi)始考慮題目：如何判斷一個(gè)測(cè)速點(diǎn)是否影響當(dāng)前最優(yōu)時(shí)間？

還是從圖上看，當(dāng)一個(gè)點(diǎn)入侵了前面那個(gè)畫(huà)法作出來(lái)的三角形的時(shí)候，最優(yōu)行駛方案就需要根據(jù)這個(gè)測(cè)速點(diǎn)進(jìn)行調(diào)整了：

當(dāng)然如果當(dāng)前測(cè)速點(diǎn)沒(méi)有入侵任何一段這樣的圖形，那么就說(shuō)這個(gè)測(cè)速點(diǎn)無(wú)效，輸出0，并且什么都不做。

現(xiàn)在考慮兩個(gè)問(wèn)題：

• 如何維護(hù)這樣的一系列圖形，使得復(fù)雜度正確？

• 題目給的測(cè)速點(diǎn)是(S, V)，怎么拿到它在v-t圖上的位置？

對(duì)于第一個(gè)問(wèn)題，其實(shí)我們發(fā)現(xiàn)只需要維護(hù)關(guān)鍵測(cè)速點(diǎn)關(guān)于距離的序列，每次新加入一個(gè)測(cè)速點(diǎn)只需要二分就能得到它受哪一段制約，這樣就能保證復(fù)雜度正確。實(shí)現(xiàn)可以按官方題解說(shuō)的用一個(gè)map來(lái)維護(hù)。

對(duì)于第二個(gè)問(wèn)題，本人的思路巨略復(fù)雜，開(kāi)始化式子：

式子中只有t1和t2是未知的，聯(lián)立距離公式和速度公式，化簡(jiǎn)后解出關(guān)于t1的一元二次方程：

先搬一個(gè)解二元一次方程的輪子：

解這個(gè)方程，可以得到分界點(diǎn)的位置，這樣我們可以得到一個(gè)分段函數(shù)，對(duì)于區(qū)間[x1, x2]，我們先判斷S在分界點(diǎn)的哪一側(cè)，然后用勻加速度位移公式：解出車車到S這點(diǎn)需要的時(shí)間，然后可以算出原圖中在這點(diǎn)的速度。如果這個(gè)速度要小于等于新建限速點(diǎn)規(guī)定的速度，那么就可以輸出0啦。

如果影響，則要修改前面說(shuō)的map，因?yàn)樾虏迦氲南匏冱c(diǎn)可能會(huì)使兩側(cè)的點(diǎn)變?yōu)闊o(wú)效限速點(diǎn)，如圖

具體實(shí)現(xiàn)就是先定位S將要插入的兩側(cè)節(jié)點(diǎn)，然后一直處理到這個(gè)連線斜率絕對(duì)值小于等于A就行了，但是實(shí)際上我們不能直接獲得它在時(shí)間軸上的位置，所以還是得繼續(xù)解二元一次方程……

另外，將起點(diǎn)和終點(diǎn)視為一個(gè)限速為0的起始限速點(diǎn)，再特判掉0和L處的限速點(diǎn)，就不用擔(dān)心邊界問(wèn)題了。

這么做的話，每個(gè)點(diǎn)最多被插入一次刪除一次均攤下來(lái)的操作一共是的，算上map的復(fù)雜度，是，可以通過(guò)本題。

完整代碼：（板子很長(zhǎng)，你們?nèi)桃幌拢?/span>

https://paste.ubuntu.com/p/hzSNkBmxy6/

表現(xiàn)：