[問題] HappyStorm's Sock Sucks

[williamd4112 (Williamd)]

身邊找不到人討論題目...幸好還有這裡
原題目：(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
推 LPH66: 你的做法就是 O(nlogn)
→ LPH66: 再一個提示好了: O(nlogn) 會 TLE 所以得用 O(n) 法
→ LPH66: 這代表每一個輸入只能用 O(1) 處理
→ LPH66: 有什麼方法可以讓每個輸入都是 O(1) 處理時間呢?
→ LPH66: 注意輸入資料的限制!
→ williamd4112: 會變成nlogn是因為我在處理輸入資料時多了一個map查
→ williamd4112: 查詢的動作嗎？
→ williamd4112: 阿...不好意思,問了廢話...
→ williamd4112: 改成先把所有可能的name以及一個sizeMap放入map
→ williamd4112: 再讀取輸入時直接sockMap[name][size]++去遞增次數
→ williamd4112: 最後traverse map一次輸出.依然TLE...QQ
→ flere: map操作就是logn呀,你可以想想不要用map怎麼做
→ williamd4112: 謝謝提示！目前用陣列四維陣列儲存次數已經不會TLE
推 hinet60613: 應該可以不用完整的紀錄襪子數? 只要紀錄有哪些襪子還
→ hinet60613: 沒成對就好，跟目前input成對的就把他從未成對中移掉
→ williamd4112: ？！樓上可以再說得更詳細點嗎
推 guest2: 仔細看的話會發現襪子的種類有限
→ williamd4112: http://pastebin.com/UTiBZPV5 目前的code
→ williamd4112: 想請問這樣再處理輸入時應該是O(1)了？(直接隨機存
→ williamd4112: 取到紀錄次數的位置(ps:剛剛看到RE,以為已經沒tle..
→ scwg: Well, 如果有兩雙成對的襪子輸出是錯的, 不過看不出來哪裡RE
→ scwg: RE; 一個可能是 stdio 和 iostream 混用又沒有
→ scwg: ios_base::sync_with_stdio() 結果讀錯東西
→ hinet60613: Input        尚未成對
→ hinet60613: (xdx X)      (xdx X)
→ hinet60613: (xdx X)      none          //以成對，故移出
→ hinet60613: (xdx X)      (xdx X)
→ hinet60613: (xdd XL)     (xdx X)(xdd XL)
→ hinet60613: (xdd S)      (xdx X)(xdd XL)(xdd S)
→ hinet60613: (xdd M)      (xdx X)(xdd XL)(xdd S)(xdd M)
→ hinet60613: 以第一筆測資來講，大概是長這個樣子
→ hinet60613: 只要記錄尚未成對的襪子就可以了，最後把尚未成對的
→ hinet60613: 襪子按照題意做排序輸出就可以了，不用記錄每一種襪子
→ hinet60613: 出現了幾支
→ hinet60613: @williamd 你的code在line37的部分會出問題，@scwg說
→ hinet60613: 的應該就是這個問題，如果有複數雙成對襪子會輸出超過
→ hinet60613: 一次的 Socks fine.
→ hinet60613: 試試這個測資 http://pastebin.com/42wFL8WU
→ williamd4112: @hinet60613:阿...我誤解題意(以為成對就fine...
→ williamd4112: 可是如果要紀錄未成對的襪子,又必須在o(1)的複雜度
→ williamd4112: 找到尚未成對的襪子然後移出
→ williamd4112: 那應該用什麼結構來儲存比較好呢？
→ williamd4112: 之前我是把name的3個字母對a的offse以及size當作索
→ williamd4112: 引,不過,這樣再輸出時又需要全部遍歷一次(雖然次數
→ williamd4112: 不算太大(26*26*26*5), 但還是跑了TLE...
推 EdisonX: bitset   擅用flip
→ williamd4112: 感謝各位,剛剛發現問題了...我把output修正過後就ac
→ williamd4112: 了,原來,跑錯的output也有可能跑到TLE QQ