沒錯，剛纔的猜想是憑直覺和量筆算搞出來的。

要想驗證自己的猜想，除了數學證明，最實用的方式就是對拍。

所謂對拍程序，通俗的說法，就是數據比較。

方法很簡單。

將窮舉暴力搜索版本的代碼，編譯可執行文件a；

將運用了猜想，優化後的代碼編譯b；

然後編寫一個隨機數據生，命名爲rand；

接下來，就可以製作對拍程序了。

代碼的主是個有限次的循環。

循環部，核心部分是幾個 system（）函數。

先調用“./rand“生隨機數據，存s.in，再分別調用a、b，讀取s.in，輸出a.out 和b.out兩個文本文件。

最後調用“diff a.out b.out“，進行比較。

如果發現兩個文本文件不一致，則說明優化後的程序有問題，於是提示錯誤信息以及出錯原因。

這就是對拍，號稱最強的調試辦法，比GDB之類的調試工好用多了。

江寒寫完對拍之後，設了一個60000次的循環，花了2分多鐘跑完一遍。

結果沒有輸出任何錯誤信息，這表示自己的猜想是完全立的。

下一步，就該把優化後的代碼擴展到高度了。

這一步對很多選手來說，都是個難點，很容易大意之下，寫一些條件。

比如位數的最大值理得不好，或者犯下其他的小失誤，就會導致運算出bug。

倒也不一定完全不能運行，只是到特殊數據時，可能會得出不正確的輸出。

運氣好的時候，也能正常得分，運氣差一點，可能就會丟分了。

高度運算的基本原理，是模擬手工列豎式計算，其中要考慮數位對齊和進位、借位理。

這種代碼在網上有的是，但運算效率上，那些比較常見的代碼，就有點不敢恭維了。

江寒在刷《NOIP寶典》的時候，自己研究出來了一種高度算法，可以說是不傳之，比網上能找到的示範代碼，要簡和巧妙很多。

在這道題裡，江寒要做的就是模擬手算高度乘除法。

如果不打高度，那麼最多僅能滿足40%的數據要求。

這道題滿分100，能看懂題目，並寫出暴力搜索算法，就能20分。

能發現規律，寫出快速排序，就能得到40分。

對於實力有限，有自知之明的選手，做到這裡就可以收手了。

只有那些對自己足夠自信，且能練編寫代碼進行高度運算的人，纔會繼續改造算法，以衝擊高分。

高度的乘法好寫，除法就稍微有點難度了。

這裡又有兩種選擇，一個是寫高除高，滿足100%的輸數據要求。

要麼就退而求其次，被除數爲高度，除數爲單度，這樣也可以滿足至60%的輸數據要求。

寫對高除以單，能得60分，寫出高除以高，纔有機會得到滿分。

但高除以高，是相當複雜的，一旦寫錯、寫了條件，說不定反而得不償失，連60分都得不到。

所以，是保證到手60分，還是冒著浪費時間的風險，衝擊一下滿分？

對於其他人來說，這當然是個艱難的抉擇，但對於江寒來說，本無需糾結。

反正時間也有的是，當然是選擇後者了。

江寒花了大約半個小時，寫出了雙高除法的版本，並調試通過。

然後設計了幾組極限數值，代進去運算，結果與筆算結果完全一致。

邊界條件沒問題，這個程序出問題的機率就相當低了。

倒也不是不能用系統作弊。

做出搜程序後，可以通過20%的校驗點，系統就提示了一次獲得“學以致用”積分。

運用了猜想，改爲快速排序後，系統再次提示，獲得了“學以致用”積分。

改高度後，系統也有獲得更多積分的提示。

這說明，江寒對程序做出的每次改進，都能使其通過更多的校驗點。

但系統的幫助也只能到這裡了，只能據此判斷出，每個步驟中的程序，都是可以得分的，卻無法判斷出是否能得到滿分。

江寒只能依靠自己富的編程經驗，儘可能保證程序無BUG。

搞定了前兩道題後，時間已經過去了1個半小時。

剩下的兩個小時，全部給最難的第三題。

題目是《開車旅行》。

題目概述：將N個城市編號爲1~N，編號小的城市在編號較大的城市之西。

各個城市海拔都不一樣，城市i的海拔爲Hi，城市i與j之間的距離d【i，j】爲兩城市海拔之差的絕對值。

也就是說d【i，j】=-Hi-Hj-。

A、B二人流開車，從A開始，每日換。

選擇一個城市S爲起點，一直向東，最多行駛X公里，就結束。

A、B駕駛風格不同，B總是沿著前進方向，選擇最近的城市作爲目的地，A總是沿著前進方向，選擇第二近的城市作爲目的地。

PS：如果兩個城市距離相同，則海拔低的視爲較近。

如果其中任何一人，無法按照自己的原則選出目的地，或者到達目的地會使公里總數超過X，就結束旅行。

輸文件中包含如下容：城市N的數目，城市1~N的海拔高度，X0，M組Si和Xi。

輸出文件中，要求回答兩個問題。

1、對於給定的X=X0，從哪一個城市出發，A開車行駛的路程與B開車行駛的路程比值最小？

2、對於任意給定的X=Xi和出發城市Si，A、B開車行駛的路程總數是多？

說實話，這道題的難點，主要在於題目的表述比較複雜。

一般人看懂題目，就至需要15分鐘……

江寒也足足花了5分鐘，才搞清楚題目的意思。

但如果讓他評價這道題的難度……

勉強3星吧。

這個題目的簡單之在於，哪怕用最笨拙的辦法，寫個暴力搜索程序，都能保底70分。

可以說是白給。

但如果想拿滿分，難度直接飆升到天際。

畢竟題目中規定：對於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互不相同。

江寒很想吐槽，海拔的上限是10億，這麼高的地方，肯定不在地球上吧？

而海拔的下限-10億，這已經LOW穿地心了喂！

好吧，又是一個“艱難”的選擇，到底是穩定拿70分，還是冒著巨大的風險，衝擊更高的分數？

這道題的關鍵仍然是數據預理。

預理得好，直接難度減半。

關於預理，有很多可行的辦法，離散化+鏈表、雙向鏈表、平衡樹……

甚至STL的set都可以。

但不能用複雜度爲O（n^2）的算法，那樣很容易在校驗時，時間超限。

畢竟據規定，每個校驗點只有1秒的運算時間。