推 intotherain:離散嗎? 59.113.165.110 02/05
推 buffalobills:如此 divide-and-conquer並不會比暴力法快 24.4.237.6 02/05
> -------------------------------------------------------------------------- <
作者: buffalobills (TKO) 看板: C_and_CPP
標題: Re: [問題] ACM 105
時間: Sat Feb 5 19:19:26 2005
※ 引述《lovehoward (Howard)》之銘言：
: ACM 105: http://acm.uva.es/p/v1/105.html
: 我的解法，可以說是暴力解吧！
: 就是建立一個大小10000的short(為了省記憶體)陣列，
: 然後把每個位置最高的房子記錄下來，
: 速度還好，可是記憶體要花456 K。
: 我看排行榜的人，每一個都只花了64k，速度還比我快，
: 是不是有更好的算法呢？
: 我只找到另一個人的原始檔，可是他的解法跟我一樣…
解這題時要利用到 input 是 sorted by L(i). ( 這題其實不像正式比賽時的題目
解釋那麼清楚, 例如, 沒有提到 L 值會不會相同, 如果可以相同, 是如何 sort )
基本上的方法是邊比較 L 值最小的兩個 input, 邊 output 結果. 原則如下:
若目前最小的 L 值有超過一筆 input, 假設其中 H 值最高的是 H(x), 則
保留 ( L(x) H(x) R(x) ) 這個 input, 並修正其他幾筆 input 的 L 值為 R(x),
例如, 改 ( L(y) H(y) R(y) ) 為 ( R(x) H(y) R(y) ), 當然, 若 R(x) >= R(y),
直接刪除 y 這個 input.
否則取 L 值最小的兩個 input (L1 H1 R1) 及 (L2 H2 R2), 假設 L1 < L2:
(1) R1 < L2 ==> print "L1 H1 R1 0 L2", 刪除 input (L1 H1 R1)
(2) R1 = L2 ==> print "L1 H1 R1", 刪除 input (L1 H1 R1)
(3) R1 > L2 且 H1 = H2 ==> 合併兩個 input
(4) R1 > L2 且 H1 < H2 ==> print "L1 H1 L2", 刪除 input (L1 H1 R1),
如果 R1 > R2, 加入 input (R2 H1 R1)
(5) R1 > L2 且 H1 > H2 ==> 刪除 input (L2 H2 R2), 如果 R2 > R1, 加入
input (R1 H2 R2)
當然在 print 結果時, 要避免重覆同一個座標, 也就是第一次之後的 output
不再 print 第一個座標. 另外, 如果有兩筆以上 input 是有相同的 L2 值,
也是用上面的原則.
用這題給的 sample input 來解釋會比較清楚:
(a) 前兩筆 input 是 (1 11 5) 及 (2 6 7), 根據 (5), 刪除 (2 6 7) 這個 input,
加入新的 input (5 6 7).
(b) 接下來 L 值最小的兩個 input 是 (1 11 5) 及 (3 13 9), 根據 (4), print
結果 "1 11 3", 刪除 input (1 11 5).
(c) 接著的兩筆是 (3 13 9) 及 (5 6 7), 根據 (5), 刪除 (5 6 7).
(d) 再下來的兩個 input 是 (3 13 9) 和 (12 7 16), 根據 (1), 刪除 (3 13 9),
output "13 9 0 12", 目前的 print 出的結果是 "1 11 3 13 9 0 12".
(e) input (12 7 16), (14 3 25). 根據 (5), 刪除 (14 3 25), 加入 (16 3 25)
(f) input (12 7 16), (16 3 25). 根據 (2), 刪除 (12 7 16), print "7 16",
目前的結果是 "1 11 3 13 9 0 12 7 16".
(g) input (16 3 25), (19 18 22), 根據 (4), 刪除 (16 3 25), 加入 (22 3 25),
print "3 19", 目前的結果是 "1 11 3 13 9 0 12 7 16 3 19".
(h) input (19 18 22), (22 3 25), 根據 (2), 刪除 (19 18 22), print "18 22"
目前的結果是 "1 11 3 13 9 0 12 7 16 3 19 18 22".
(i) input (22 3 25), (23 13 29), 根據 (4), 刪除 (22 3 25), print "3 23",
目前的結果是 "1 11 3 13 9 0 12 7 16 3 19 18 22 3 23".
(j) input (23 13 29), (24 4 28), 根據 (5), 刪除 (24 4 28)
(k) input (23 13 29), 刪除這個 input, print "13 29", 目前的結果是
"1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29".
(l) 沒有 input, print "0" 為結尾
如此可得 output "1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0"
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 24.4.237.6
推 sekya:nice!! thx. 220.142.6.236 02/05
※ 編輯: buffalobills 來自: 24.4.237.6 (02/06 03:36)
推 lovehoward:謝謝！我完全沒有想到兩個建築處理後 61.59.131.95 02/06
→ lovehoward:可以再用一個建築去補！ 61.59.131.95 02/06