#40953: 不用模擬 Time: O(n) Space: O(R)


ericshen19555@gmail.com (暴力又被TLE)

學校 : 南光中學
編號 : 103121
來源 : [111.254.38.239]
最後登入時間 :
2024-11-10 22:57:03
j123. 2. 運貨站 -- 2022年10月APCS | From: [210.71.26.21] | 發表日期 : 2024-06-21 12:38

這題乍看之下是挺難寫的模擬題,最直觀的做法是將各種形狀的貨物從最右邊一直往左塞,直到碰到底或者其他貨物。
此時如何將貨物編碼並偵測是否碰撞是很麻煩的問題,而且從最右邊持續往左塞的方法,在數值變大以後複雜度會爆掉(但這題不會有這個問題,可以考慮加一題測資加強版)

但因為這題固定是從最右邊往左,所以可以想出一種方法:
貨櫃的部分只需要紀錄每一行最右邊一格的貨物(簡單來講就是已經被塞得多滿了)
像是以下這個例子(_表空格 #表貨物)
_ _ _ _ _ _ -> 0
# # _ _ _ _ -> 2
# # # _ _ _ -> 3
_ _ # # _ _ -> 4
就會儲存為 [0, 2, 3, 4]

那如何編碼貨物並根據倉庫狀態,在O(1)得出貨物該塞多深? (其實理論上是O(貨物高度),但這題的貨物固定且都很小,視為常數)
首先觀察貨物,右邊都是切期的一條線 (這個特性很重要,如果沒有的話比較難寫,可以自己想想看(・∀・))
那我們就可以很直接的將貨物依照每一行的寬度編碼:
像是貨物E就可以編碼成 [1, 2, 2]
  @ -> 1
@ @ -> 2
@ @ -> 2
那接下來就簡單了,只要根據給定的y將貨物對準倉庫後,算"每一行的貨物塞進去後,該行倉庫至少會變多滿"就好了
舉例: 以下這個情況再塞一個 E, y=1
_ _ _ _ _ _ |     -> 0
# # _ _ _ _ |   @ -> 2 + 1 = 3
# # # _ _ _ | @ @ -> 3 + 2 = 5
_ _ # # _ _ | @ @ -> 4 + 2 = 6
"切成一行行去討論"視覺化來講就是這樣:
_ _ _ _ _ _  -> 0
# # @ _ _ _  -> 2 + 1 = 3
# # # @ @ _  -> 3 + 2 = 5
_ _ # # @ @  -> 4 + 2 = 6
貨物不能拆開,所以結果應該是
_ _ _ _ _ _  -> 0
# # _ _ _ @  -> 6
# # # _ @ @  -> 6
_ _ # # @ @  -> 6
也就是這整個區間都更新成 max(3, 5, 6) = 6  (因為右邊切齊,所以才能直接這樣做)
判斷塞不進去的情況,那就是max後取區來的結果 > C (倉庫寬度)

就醬。

 
ZeroJudge Forum