NOIP2012提高組 開車旅行 題解

題目連接配接：https://www.luogu.org/problem/show?pid=1081

題目描述：

小 A 和小 B 決定利用假期外出旅行，他們将想去的城市從 1 到 N 編号，且編号較小的城市在編号較大的城市的西邊，已知各個城市的海拔高度互不相同，記城市 i 的海拔高度為Hi，城市 i 和城市 j 之間的距離 d[i,j]恰好是這兩個城市海拔高度之差的絕對值，即d[i,j] = |Hi− Hj|。

旅行過程中，小 A 和小 B 輪流開車，第一天小 A 開車，之後每天輪換一次。他們計劃選擇一個城市 S 作為起點，一直向東行駛，并且最多行駛 X 公裡就結束旅行。

小 A 和小 B的駕駛風格不同，小 B 總是沿着前進方向選擇一個最近的城市作為目的地，而小 A 總是沿着前進方向選擇第二近的城市作為目的地（注意：本題中如果目前城市到兩個城市的距離相同，則認為離海拔低的那個城市更近）。

如果其中任何一人無法按照自己的原則選擇目的城市，或者到達目的地會使行駛的總距離超出 X 公裡，他們就會結束旅行。

在啟程之前，小 A 想知道兩個問題：

1．對于一個給定的 X=X0，從哪一個城市出發，小 A 開車行駛的路程總數與小 B 行駛的路程總數的比值最小（如果小 B 的行駛路程為 0，此時的比值可視為無窮大，且兩個無窮大視為相等）。

2 .  如果從多個城市出發，小 A 開車行駛的路程總數與小 B 行駛的路程總數的比值都最小，則輸出海拔最高的那個城市。對任意給定的 X=Xi和出發城市 Si，小 A 開車行駛的路程總數以及小 B 行駛的路程總數。

【資料範圍】對于100%的資料，有1≤N≤100,000，1≤M≤10,000，-1,000,000,000≤Hi≤1,000,000,000，0≤X0≤1,000,000,000，1≤Si≤N，0≤Xi≤1,000,000,000，資料保證 Hi互不相同。

總思想：二分

f[i][j]表示從節點i出發，A和B總共走2^j步的一些狀态，比如：

f[i][j][0]表示2^j後，A總共走的距離

f[i][j][1]表示2^j後，B總共走的距離

f[i][j][2]表示2^j後，A+B總共走的距離

f[i][j][3]表示2^j後，到達的節點坐标

倍增方程f[i][j] = f[f[i][j-1][3]][j-1]   即從i出發，先走2^j-1步，到達點x，然後繼續走2^j-1步，總共走了2^(j-1)+2^(j-1)=2^j步。

這樣隻要求出f[i][0]及f[i][1]就可以求出所有的f[i][j]。（這道題，f[i][0]有點特别，我這裡專指A走1步，是以是從f[i][1]推倒到f[i][j]的，而不是f[i][0]開始推倒）

接下來就是預處理了：如何快速求出每個點出發的最近點以及次近點？

按高度快排，同時記錄編号為i的城市，最後在快排序列的什麼位置。

假設這個排序序列是a1,a2,a3,…an。則，對于ai這個城市，如果所有編号<ai的城市最近點以及次近點都已經求出，并且不在這個排序序列中，那麼城市ai的最近點以及次近點一定在ai-2 ai-1ai+1 ai+2中的兩個。将這個4個城市進行判斷，得出解以後，其實這個城市ai已經沒用了，可以從序列中删除以保證後面能也同樣處理。

是以我們隻需将這個快排以後的序列存儲到連結清單中，并且從編号小的點處理到編号大的點，邊處理邊删除即可求出所有城市的最近點以及次近點。複雜度O(4n)

預處理複雜度O(4n+nlogn)，完全可以接受并且很理想。

接下來考慮如何處理問題1：

其實很簡單，周遊所有城市，計算出以城市i出發行走X0距離，小A及小B行走的距離差即可。

假設行走X0距離，AB總共需開T次車，則即是如何快速求這個T的問題，因為求出來以後直接用之前通過倍增得到的狀态數組就可以算出需要的距離差了。

不妨将T看做一個二進制數，則就是如何快速從T轉成二進制的問題了，因為f數組就是存了二進制下，二進制各位的狀态。是以logN的代價内就能求出這個T，因為最多就是走N步。是以第一個問題的複雜度是O(NlogN)

接下來考慮如何處理問題2：

第二問隻是問題比較多而已啦，但是每個小問題和第一問沒什麼差別，而且複雜度更低。是以隻需求解這個M個問題就行了，O(MlogN)。