作者williamd4112 (Williamd)
看板Prob_Solve
標題[問題] HappyStorm's Sock Sucks
時間Wed Jan 28 21:44:07 2015
身邊找不到人討論題目...幸好還有這裡
原題目：(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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1422452649.A.834.html
1F：推 LPH66: 你的做法就是 O(nlogn) 01/28 21:51
2F：→ LPH66: 再一個提示好了: O(nlogn) 會 TLE 所以得用 O(n) 法 01/28 21:52
3F：→ LPH66: 這代表每一個輸入只能用 O(1) 處理 01/28 21:52
4F：→ LPH66: 有什麼方法可以讓每個輸入都是 O(1) 處理時間呢? 01/28 21:52
5F：→ LPH66: 注意輸入資料的限制! 01/28 21:53
6F：→ williamd4112: 會變成nlogn是因為我在處理輸入資料時多了一個map查 01/28 22:02
7F：→ williamd4112: 查詢的動作嗎？ 01/28 22:02
8F：→ williamd4112: 阿...不好意思,問了廢話... 01/28 22:06
9F：→ williamd4112: 改成先把所有可能的name以及一個sizeMap放入map 01/28 22:34
10F：→ williamd4112: 再讀取輸入時直接sockMap[name][size]++去遞增次數 01/28 22:34
11F：→ williamd4112: 最後traverse map一次輸出.依然TLE...QQ 01/28 22:35
12F：→ flere: map操作就是logn呀,你可以想想不要用map怎麼做 01/28 22:39
13F：→ williamd4112: 謝謝提示！目前用陣列四維陣列儲存次數已經不會TLE 01/28 23:05
14F：推 hinet60613: 應該可以不用完整的紀錄襪子數? 只要紀錄有哪些襪子還 01/28 23:13
15F：→ hinet60613: 沒成對就好，跟目前input成對的就把他從未成對中移掉 01/28 23:14
16F：→ williamd4112: ？！樓上可以再說得更詳細點嗎 01/29 00:34
17F：推 guest2: 仔細看的話會發現襪子的種類有限 01/29 00:41
19F：→ williamd4112: 想請問這樣再處理輸入時應該是O(1)了？(直接隨機存 01/29 01:19
20F：→ williamd4112: 取到紀錄次數的位置(ps:剛剛看到RE,以為已經沒tle.. 01/29 01:20
21F：→ scwg: Well, 如果有兩雙成對的襪子輸出是錯的, 不過看不出來哪裡RE 01/29 02:22
22F：→ scwg: RE; 一個可能是 stdio 和 iostream 混用又沒有 01/29 02:23
23F：→ scwg: ios_base::sync_with_stdio() 結果讀錯東西 01/29 02:23
24F：→ hinet60613: Input 尚未成對 01/29 15:38
25F：→ hinet60613: (xdx X) (xdx X) 01/29 15:39
26F：→ hinet60613: (xdx X) none //以成對，故移出 01/29 15:39
27F：→ hinet60613: (xdx X) (xdx X) 01/29 15:39
28F：→ hinet60613: (xdd XL) (xdx X)(xdd XL) 01/29 15:39
29F：→ hinet60613: (xdd S) (xdx X)(xdd XL)(xdd S) 01/29 15:40
30F：→ hinet60613: (xdd M) (xdx X)(xdd XL)(xdd S)(xdd M) 01/29 15:40
31F：→ hinet60613: 以第一筆測資來講，大概是長這個樣子 01/29 15:40
32F：→ hinet60613: 只要記錄尚未成對的襪子就可以了，最後把尚未成對的 01/29 15:40
33F：→ hinet60613: 襪子按照題意做排序輸出就可以了，不用記錄每一種襪子 01/29 15:41
34F：→ hinet60613: 出現了幾支 01/29 15:41
35F：→ hinet60613: @williamd 你的code在line37的部分會出問題，@scwg說 01/29 15:48
36F：→ hinet60613: 的應該就是這個問題，如果有複數雙成對襪子會輸出超過 01/29 15:49
37F：→ hinet60613: 一次的 Socks fine. 01/29 15:49
39F：→ williamd4112: @hinet60613:阿...我誤解題意(以為成對就fine... 01/29 16:42
40F：→ williamd4112: 可是如果要紀錄未成對的襪子,又必須在o(1)的複雜度 01/29 16:44
41F：→ williamd4112: 找到尚未成對的襪子然後移出 01/29 16:45
42F：→ williamd4112: 那應該用什麼結構來儲存比較好呢？ 01/29 16:45
43F：→ williamd4112: 之前我是把name的3個字母對a的offse以及size當作索 01/29 16:47
44F：→ williamd4112: 引,不過,這樣再輸出時又需要全部遍歷一次(雖然次數 01/29 16:48
45F：→ williamd4112: 不算太大(26*26*26*5), 但還是跑了TLE... 01/29 16:48
46F：推 EdisonX: bitset 擅用flip 01/29 20:01
47F：→ williamd4112: 感謝各位,剛剛發現問題了...我把output修正過後就ac 01/30 01:21
48F：→ williamd4112: 了,原來,跑錯的output也有可能跑到TLE QQ 01/30 01:22