身邊找不到人討論題目...幸好還有這裡
原題目：(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)會超時的用意為何...

你的做法就是 O(nlogn)再一個提示好了: O(nlogn) 會 TLE 所以得用 O(n) 法這代表每一個輸入只能用 O(1) 處理有什麼方法可以讓每個輸入都是 O(1) 處理時間呢?注意輸入資料的限制!

會變成nlogn是因為我在處理輸入資料時多了一個map查查詢的動作嗎？阿...不好意思,問了廢話...改成先把所有可能的name以及一個sizeMap放入map再讀取輸入時直接sockMap[name][size]++去遞增次數最後traverse map一次輸出.依然TLE...QQ

map操作就是logn呀,你可以想想不要用map怎麼做

謝謝提示！目前用陣列四維陣列儲存次數已經不會TLE

應該可以不用完整的紀錄襪子數? 只要紀錄有哪些襪子還沒成對就好，跟目前input成對的就把他從未成對中移掉

？！樓上可以再說得更詳細點嗎

仔細看的話會發現襪子的種類有限

http://pastebin.com/UTiBZPV5 目前的code想請問這樣再處理輸入時應該是O(1)了？(直接隨機存取到紀錄次數的位置(ps:剛剛看到RE,以為已經沒tle..

Well, 如果有兩雙成對的襪子輸出是錯的, 不過看不出來哪裡RERE; 一個可能是 stdio 和 iostream 混用又沒有ios_base::sync_with_stdio() 結果讀錯東西

Input 尚未成對(xdx X) (xdx X)(xdx X) none //以成對，故移出(xdx X) (xdx X)(xdd XL) (xdx X)(xdd XL)(xdd S) (xdx X)(xdd XL)(xdd S)(xdd M) (xdx X)(xdd XL)(xdd S)(xdd M)以第一筆測資來講，大概是長這個樣子只要記錄尚未成對的襪子就可以了，最後把尚未成對的襪子按照題意做排序輸出就可以了，不用記錄每一種襪子出現了幾支@williamd 你的code在line37的部分會出問題，@scwg說的應該就是這個問題，如果有複數雙成對襪子會輸出超過一次的 Socks fine.試試這個測資 http://pastebin.com/42wFL8WU

@hinet60613:阿...我誤解題意(以為成對就fine...可是如果要紀錄未成對的襪子,又必須在o(1)的複雜度找到尚未成對的襪子然後移出那應該用什麼結構來儲存比較好呢？之前我是把name的3個字母對a的offse以及size當作索引,不過,這樣再輸出時又需要全部遍歷一次(雖然次數不算太大(26*26*26*5), 但還是跑了TLE...

bitset 擅用flip

感謝各位,剛剛發現問題了...我把output修正過後就ac了,原來,跑錯的output也有可能跑到TLE QQ