PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] HappyStorm's Sock Sucks

看板Prob_Solve (計算數學 Problem Solving)作者 (Williamd)時間10年前 (2015/01/28 21:44), 編輯推噓4(4推 0噓 44→)
留言48則, 7人參與, 最新討論串1/1
身邊找不到人討論題目...幸好還有這裡 原題目：(nthu_oj) ※先聲明這不是作業,只是自己的練習 http://acm.cs.nthu.edu.tw/problem.php?pid=7667 這題我的作法是把襪子宣告成一個struct來儲存name,size struct Sock{ string name,size; } 然後定義operator <(less than operator) 再把struct(襪子)跟int(次數)存到map裏 用讀進來的name, size建立struct, 插入到map中 如果已經在map中,則次數遞增 如果不在,則初始化為1 測試結果是正確的, 但超時... 想請問有什麼方法可以做更快？ (不知道他題目中給的hint: O(nlogn)會超時的用意為何... -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.114.196.141 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1422452649.A.834.html
推
01/28 21:51, , 1F
你的做法就是 O(nlogn)
01/28 21:51, 1F
→
01/28 21:52, , 2F
再一個提示好了: O(nlogn) 會 TLE 所以得用 O(n) 法
01/28 21:52, 2F
→
01/28 21:52, , 3F
這代表每一個輸入只能用 O(1) 處理
01/28 21:52, 3F
→
01/28 21:52, , 4F
有什麼方法可以讓每個輸入都是 O(1) 處理時間呢?
01/28 21:52, 4F
→
01/28 21:53, , 5F
注意輸入資料的限制!
01/28 21:53, 5F
→
01/28 22:02, , 6F
會變成nlogn是因為我在處理輸入資料時多了一個map查
01/28 22:02, 6F
→
01/28 22:02, , 7F
查詢的動作嗎？
01/28 22:02, 7F
→
01/28 22:06, , 8F
阿...不好意思,問了廢話...
01/28 22:06, 8F
→
01/28 22:34, , 9F
改成先把所有可能的name以及一個sizeMap放入map
01/28 22:34, 9F
→
01/28 22:34, , 10F
再讀取輸入時直接sockMap[name][size]++去遞增次數
01/28 22:34, 10F
→
01/28 22:35, , 11F
最後traverse map一次輸出.依然TLE...QQ
01/28 22:35, 11F
→
01/28 22:39, , 12F
map操作就是logn呀,你可以想想不要用map怎麼做
01/28 22:39, 12F
→
01/28 23:05, , 13F
謝謝提示！目前用陣列四維陣列儲存次數已經不會TLE
01/28 23:05, 13F
推
01/28 23:13, , 14F
應該可以不用完整的紀錄襪子數? 只要紀錄有哪些襪子還
01/28 23:13, 14F
→
01/28 23:14, , 15F
沒成對就好，跟目前input成對的就把他從未成對中移掉
01/28 23:14, 15F
→
01/29 00:34, , 16F
？！樓上可以再說得更詳細點嗎
01/29 00:34, 16F
推
01/29 00:41, , 17F
仔細看的話會發現襪子的種類有限
01/29 00:41, 17F
→
01/29 01:18, , 18F
01/29 01:18, 18F
→
01/29 01:19, , 19F
想請問這樣再處理輸入時應該是O(1)了？(直接隨機存
01/29 01:19, 19F
→
01/29 01:20, , 20F
取到紀錄次數的位置(ps:剛剛看到RE,以為已經沒tle..
01/29 01:20, 20F
→
01/29 02:22, , 21F
Well, 如果有兩雙成對的襪子輸出是錯的, 不過看不出來哪裡RE
01/29 02:22, 21F
→
01/29 02:23, , 22F
RE; 一個可能是 stdio 和 iostream 混用又沒有
01/29 02:23, 22F
→
01/29 02:23, , 23F
ios_base::sync_with_stdio() 結果讀錯東西
01/29 02:23, 23F
→
01/29 15:38, , 24F
Input 尚未成對
01/29 15:38, 24F
→
01/29 15:39, , 25F
(xdx X) (xdx X)
01/29 15:39, 25F
→
01/29 15:39, , 26F
(xdx X) none //以成對，故移出
01/29 15:39, 26F
→
01/29 15:39, , 27F
(xdx X) (xdx X)
01/29 15:39, 27F
→
01/29 15:39, , 28F
(xdd XL) (xdx X)(xdd XL)
01/29 15:39, 28F
→
01/29 15:40, , 29F
(xdd S) (xdx X)(xdd XL)(xdd S)
01/29 15:40, 29F
→
01/29 15:40, , 30F
(xdd M) (xdx X)(xdd XL)(xdd S)(xdd M)
01/29 15:40, 30F
→
01/29 15:40, , 31F
以第一筆測資來講，大概是長這個樣子
01/29 15:40, 31F
→
01/29 15:40, , 32F
只要記錄尚未成對的襪子就可以了，最後把尚未成對的
01/29 15:40, 32F
→
01/29 15:41, , 33F
襪子按照題意做排序輸出就可以了，不用記錄每一種襪子
01/29 15:41, 33F
→
01/29 15:41, , 34F
出現了幾支
01/29 15:41, 34F
→
01/29 15:48, , 35F
@williamd 你的code在line37的部分會出問題，@scwg說
01/29 15:48, 35F
→
01/29 15:49, , 36F
的應該就是這個問題，如果有複數雙成對襪子會輸出超過
01/29 15:49, 36F
→
01/29 15:49, , 37F
一次的 Socks fine.
01/29 15:49, 37F
→
01/29 15:51, , 38F
試試這個測資 http://pastebin.com/42wFL8WU
01/29 15:51, 38F
→
01/29 16:42, , 39F
@hinet60613:阿...我誤解題意(以為成對就fine...
01/29 16:42, 39F
→
01/29 16:44, , 40F
可是如果要紀錄未成對的襪子,又必須在o(1)的複雜度
01/29 16:44, 40F
→
01/29 16:45, , 41F
找到尚未成對的襪子然後移出
01/29 16:45, 41F
→
01/29 16:45, , 42F
那應該用什麼結構來儲存比較好呢？
01/29 16:45, 42F
→
01/29 16:47, , 43F
之前我是把name的3個字母對a的offse以及size當作索
01/29 16:47, 43F
→
01/29 16:48, , 44F
引,不過,這樣再輸出時又需要全部遍歷一次(雖然次數
01/29 16:48, 44F
→
01/29 16:48, , 45F
不算太大(26*26*26*5), 但還是跑了TLE...
01/29 16:48, 45F
推
01/29 20:01, , 46F
bitset 擅用flip
01/29 20:01, 46F
→
01/30 01:21, , 47F
感謝各位,剛剛發現問題了...我把output修正過後就ac
01/30 01:21, 47F
→
01/30 01:22, , 48F
了,原來,跑錯的output也有可能跑到TLE QQ
01/30 01:22, 48F
‣ 更多 williamd4112 的文章
文章代碼(AID): #1KoEUfWq (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 williamd4112 的文章
文章代碼(AID): #1KoEUfWq (Prob_Solve)