Re: [問題] SPOJ 1774. All Discs Considered [ALL]
看板Prob_Solve (計算數學 Problem Solving)作者AmosYang (Zzz...)時間13年前 (2011/10/14 08:51)推噓2(2推 0噓 1→)留言3則, 2人參與討論串1/3 (看更多)
※ 引述《bleed1979 (十三)》之銘言：
: http://www.spoj.pl/problems/ALL/
: 推 Fenikso:模擬題. 一開始兩片選一片放, 之後的動作全部固定 10/14 02:58
: → Fenikso:各模擬一次取比較小的就是了 10/14 02:59
因為 0<=D<=100000 ，建 tree 應該不會爆 out of memory , 所以
1. 一面讀 input 就一面建 dependency tree, 一面建 tree 一面記得 tree 的高度
root node 是來自第一片 DVD 的 package 的 tree 放一邊,
同時記得目前最高的 tree
root node 是來自第二片 DVD 的 package 的 tree 放一邊,
同時記得目前最高的 tree
2. 資料讀完後，把第一組最高的 tree 與 第二組最高的 tree 拿出來比高度
比較高的 tree 的高度 +2 應該就是答案
如果兩棵樹一樣高，高度 +3 為答案
這樣應該是 O(D) 解, 應該會比直接模擬快
--
※ 發信站 :批踢踢實業坊(ptt.cc)
◆ From: 24.40.140.18
※ 編輯: AmosYang 來自: 24.40.140.18 (10/14 08:56)
直接模擬…最簡單的寫法會是 O( (n1+n2) * D )
應該可以把那個 D 壓下來，但大概沒辦法壓得跟上面說的 O(D) 一樣快
※ 編輯: AmosYang 來自: 24.40.140.18 (10/14 09:02)
推
10/14 09:03, , 1F
10/14 09:03, 1F
推
10/14 09:08, , 2F
10/14 09:08, 2F
→
10/14 09:08, , 3F
10/14 09:08, 3F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-1
12