[C_CH13-中] 坑洞路面
這題是 e-tutor 的題目,網址請點這兒。
分類上屬於中等。我個人認為這個題目的風格就像是大型比賽的風格了。乍看之下會沒有頭絮,要仔細思考後,才能發現解題的線索。
我們要輸出「總」積水量,以前述的範例來說,就是要輸出 1 + 2 + 2+ 1= 6。
第一件事,就是最「邊邊」永遠不會積水。以上圖來說,位置 0 以及位置 6 永遠不會積水。
為什麼?
因為位置 -1 以及位置 7 的高度為 0,水往低處流,所以最邊邊是不會積水的。
第二件事,不是「最邊邊」的位置,我要怎麼判斷會不會積水?
還是透過「大問題,拆小問題」的套路來解。
針對每個位置,我們要問兩個問題:
先舉一個實例來看看吧!
最後是找出 minmax,程式碼如下,這部分就更簡單了,單純由兩個數中找最小即可。
最後就可以組出完整的程式囉。
這兒我們呼叫了 max_element 來找陣列中的最大值,所以記得引入 algorithm 這個標頭檔。可以看得出來,程式碼精簡許多。
比賽時,如果可以善用 C++ 本身提供的函式庫,是可以少打許多程式碼。而且 C++ 提供的函式已經通過很嚴格的測試,可以說不會有任何的錯誤,這比自己動手來說,少了很多的問題。建議可能的話,盡可能用標準函式庫中的程式了。
分類上屬於中等。我個人認為這個題目的風格就像是大型比賽的風格了。乍看之下會沒有頭絮,要仔細思考後,才能發現解題的線索。
題目檢視
先看看題目,請配合下圖服用囉。
圖中土色的部分,代表「地表面」。
藍色的部分,代表「積水」。
最上面那排數字,代表那一格的「高度」。
最下面那排數字,代表「位置」。
所以合起來就是第 0 個位置,高度為 3, 0 積水。
第1個位置,高度為2,積水 1 格。
路面積水的示意圖 |
這題的輸出、以及輸出如下圖所示:
輸入以及輸出的範列 |
觀察
第一件事,就是最「邊邊」永遠不會積水。以上圖來說,位置 0 以及位置 6 永遠不會積水。
為什麼?
因為位置 -1 以及位置 7 的高度為 0,水往低處流,所以最邊邊是不會積水的。
第二件事,不是「最邊邊」的位置,我要怎麼判斷會不會積水?
還是透過「大問題,拆小問題」的套路來解。
針對每個位置,我們要問兩個問題:
- 針對位置 [i],我怎麼知道它「會不會」積水?
- 針對位置 [i],如果它會積水,積水有多高?
如果位置 [i] 的問題可以解決,那就可以推而廣之,把整個問題解掉了。
先舉一個實例來看看吧!
位置 [2] 會積水嗎?
我們看位置 [2] 會不會積水。
一看就知道會積水。但電腦不會「看」呀,所以我們要教它判斷的邏輯。
位置 [2] 會積水,是因為它是個凹洞。 嗯,這個回答有點接近了,但電腦還不能處理。因為「凹洞」這個詞太模糊了。電腦通常處理的是「數字」,因此我們必需把凹洞這個意思,轉成可以計算的「數字」才可以。
再問下去,「凹洞」有什麼特質?
因為位置 [2] 的高度比 (1) 左邊的高度,以及 (2) 右邊的高度,來得 小!
Bingo!這就可以解了,因為高度是個數值,電腦可以運算!
所以我們只要從位置 [2] 這個地方開始,由左,由右掃描,只要發現有比它高的路面,那位置 [2] 就會積水。
以下圖為例,箭號所指之處,就是比位置 [2] 還要高的路面,所以位置 [2] 會積水。
底下是找到某個位置左邊最大值的程式碼。
pos 代表目前所在的位置。迴圈由 0 掃到 pos,就是找 pos 左邊的最高點,也就是 lmax 了。
以上圖來說, pos 就是 [2],而迴圈就是找 [0], [1], [2],看看 lmax 為何。
底下是找 rmax 的程式碼,由於邏輯和上面是一樣的,就不多說明了。
以下圖為例,箭號所指之處,就是比位置 [2] 還要高的路面,所以位置 [2] 會積水。
位置 [2] 的高度為 1 位置 [2] 右邊比它高 (為 4) 位置 [2] 左邊比它高 (為 2) |
位置 [2] 的積水有多高?
知道位置 [2] 會積水後,那就要分析積水會有多高了。
這時要多分析幾個例子,才能確保沒有錯。
首先看下圖,直覺上可能會想說,由位置 [2] 往右邊找到比它高的地點。再往位置 [2] 左邊找比它高的地點,就會得到下圖兩個箭號的點。
我們稱位置 [2] 右邊比較高的點為 rmax,所以 rmax = 4。
我們稱位置 [2] 左邊比較高的點為 lmax,所以 lmax = 3。
然後取這兩者的最小,稱為 min_max,所以 min_max = max(rmax, lmax) = 3。
把 min_max 減去 [2] 的高度,就得到 min_max - 1 = 3 - 1 ==> 2。
於是 2 就是 [2] 的積水高度!
這種想法是錯的!
在位置 [2] 右邊,比 [2] 還要高的點為 rmax 在位置 [2] 左邊,比 [2] 還要高的點為 lmax |
看下圖囉。
如果用前述的邏輯去解的話,會發算出來 [2] 的積水為 2。
但實際上我們發現 [2] 的積水為 4 才對。
所以問題出在,我們要找的 rmax 是 [2] 右邊「最高」的點,所以實際上 rmax 為 5。
我們要找的 lmax 是 [2] 左邊「最高」的點,所以 lmax = 5。
因此 min_max = min(rmax, lmax) = 5。
所以積水為 min_max - 1 ==> 4。
可以寫 code 了
分析到這兒,可以開始寫 code 了。
首先先把資料讀入,這部分很簡單,就不解說了,直接上程式碼。
pos 代表目前所在的位置。迴圈由 0 掃到 pos,就是找 pos 左邊的最高點,也就是 lmax 了。
以上圖來說, pos 就是 [2],而迴圈就是找 [0], [1], [2],看看 lmax 為何。
底下是找 rmax 的程式碼,由於邏輯和上面是一樣的,就不多說明了。
最後是找出 minmax,程式碼如下,這部分就更簡單了,單純由兩個數中找最小即可。
最後就可以組出完整的程式囉。
更精緻的寫法
其實在陣列中找某個區間的最大值, C++ 有提供現成的 max_element 可以使用。所以我們不用自己寫。
前述程式碼中 17 行到 34 行可以簡化。
此外,求 min 也有現成的函式。所以整個程式碼可以更改如下。
這兒我們呼叫了 max_element 來找陣列中的最大值,所以記得引入 algorithm 這個標頭檔。可以看得出來,程式碼精簡許多。
比賽時,如果可以善用 C++ 本身提供的函式庫,是可以少打許多程式碼。而且 C++ 提供的函式已經通過很嚴格的測試,可以說不會有任何的錯誤,這比自己動手來說,少了很多的問題。建議可能的話,盡可能用標準函式庫中的程式了。
How much is titanium worth? - The Silicon Underground
回覆刪除Get the most baoji titanium out of your titanium price bets. We offer a huge micro touch trimmer range of our high-quality free tips for titanium hair trimmer sports betting. We cover the top titanium men\'s wedding band free tips.