[ACM ] 318done

看板C_and_CPP作者 (我不是阿見)時間15年前 (2010/05/04 18:09), 編輯推噓4(4推 0噓 26→)
留言30則, 2人參與, 最新討論串1/1
( *[1m *[m 為色碼，可以按 Ctrl+V 預覽會顯示的顏色 ) ( 未必需要依照此格式，文章條理清楚即可 ) 題號：318 給妳n個大骨牌(n<500),中間用小骨牌串連起來，每個大骨牌倒下去時 會推倒附近的小骨牌。 問推動第一個大骨牌後，最後倒下的骨牌位置。 遇到的問題： 一直WA= =||| 有問題的code： (請善用置底文的標色功能) http://codepad.org/IVldU6PZ 補充說明： 不好意思 我又來問問題了 這次輸出格式上我檢查過了 應該是沒問題了 所以想請各位大大幫看一下我的演算法是不是邏輯有錯或打錯... 謝謝!! 演算法:用Dijkstra's先找各大骨牌倒下時間 利用兩大骨牌倒下時間推算中間小骨牌倒下時間再取最大值出來 (若A倒下的時間點為t1 B倒下的時間點為t2 小骨牌倒完需要的時間為w 如果abs(t1-t2)<w 中間小骨牌倒下時間=(A+B+小骨牌需要的時間)/2 若相等的話就不計算 最後倒的必定是max(t1,t2)那邊 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.204.2.55
推
05/04 18:14, , 1F
(若A B倒下時間差小於中間小骨牌需要的時間) Why?
05/04 18:14, 1F
→
05/04 18:14, , 2F
另外 如果有覺得我code習慣不好也請指教一下 謝謝!!
05/04 18:14, 2F
→
05/04 18:14, , 3F
可輕易舉出反例吧
05/04 18:14, 3F
→
05/04 18:15, , 4F
事實上, 只要有edge相連的大骨牌, 都去做計算就可以了
05/04 18:15, 4F
→
05/04 18:15, , 5F
因為若是等於的話 那最後倒下的會是大骨牌 所以就能不理
05/04 18:15, 5F
→
05/04 18:17, , 6F
大於呢?
05/04 18:17, 6F
→
05/04 18:18, , 7F
因為是用最短路徑去找 所以理論上應該沒有大於的狀況
05/04 18:18, 7F
→
05/04 18:18, , 8F
另外就算等於, 最後倒下也不一定是大骨牌
05/04 18:18, 8F
→
05/04 18:20, , 9F
這題提供的第二個test data, 你把2 3 的距離改成50
05/04 18:20, 9F
→
05/04 18:20, , 10F
不就大於了嗎
05/04 18:20, 10F
→
05/04 18:21, , 11F
但是A B倒下時間差為0<50的
05/04 18:21, 11F
→
05/04 18:22, , 12F
ohoh, 那改成 2 3 距離 2 ?
05/04 18:22, 12F
→
05/04 18:22, , 13F
我想我說明沒寫好 我在想想怎麼說比較好
05/04 18:22, 13F
※ 編輯: ccs5271 來自: 123.204.2.55 (05/04 18:26)
推
05/04 18:25, , 14F
事實上可以很簡單驗證,無論大於等於小於,都算並不影響
05/04 18:25, 14F
→
05/04 18:25, , 15F
答案
05/04 18:25, 15F
→
05/04 18:25, , 16F
另外如果你的演算法描述沒錯, 你就是少算了大於的部份
05/04 18:25, 16F
→
05/04 18:26, , 17F
咦, 好像不對...我想想o.o
05/04 18:26, 17F
→
05/04 18:27, , 18F
我不算等於是因為我結構沒處理好 變成等於case不好處理
05/04 18:27, 18F
→
05/04 18:28, , 19F
還是我砍掉重練一個看看
05/04 18:28, 19F
推
05/04 18:30, , 20F
題外話...助教給個測資你都過了嗎?
05/04 18:30, 20F
→
05/04 18:33, , 21F
我忘了助教有給測資= = 我馬上去測Orz
05/04 18:33, 21F
→
05/04 18:40, , 22F
memset 是以 byte 為單位在設定
05/04 18:40, 22F
→
05/04 18:40, , 23F
恐怕 node[] 值並不如你想的初始為 -1
05/04 18:40, 23F
→
05/04 18:44, , 24F
噗, 真的是-1 , 看來我計概要重修了
05/04 18:44, 24F
→
05/04 18:51, , 25F
我找到錯誤了...我針對1 0的case沒有印system...
05/04 18:51, 25F
→
05/04 18:51, , 26F
又是輸出格式問題(T.T)我開始覺得我是個笨蛋了(大哭)
05/04 18:51, 26F
→
05/04 18:52, , 27F
話說這篇這樣子要刪文嗎 感覺跟程式沒有關係= =
05/04 18:52, 27F
推
05/04 18:54, , 28F
隨意吧XD 另外下次發ACM文最好附上題目連結
05/04 18:54, 28F
→
05/04 18:54, , 29F
會有更多大大幫忙
05/04 18:54, 29F
→
05/04 18:56, , 30F
恩恩 不過希望沒有下次XD(想全部自己解決的意思)
05/04 18:56, 30F
‣ 更多 ccs5271 的文章
文章代碼(AID): #1Bt_9Xt_ (C_and_CPP)