[ACM ] d550. 物件排序 TLE

[unfun (不好玩)]

        ( *[1m *[m 為色碼，可以按 Ctrl+V 預覽會顯示的顏色 )
             ( 未必需要依照此格式，文章條理清楚即可 )

題號：
http://zerojudge.tw/ShowProblem?problemid=d550

遇到的問題：

*** 第 6 點 (10%)：TLE (1s)
執行逾時(1s)!! 請檢查是否產生無限迴圈或尋找更好的演算法

有問題的code： (請善用置底文的標色功能)
不論是:
利用BinarySearchTree
http://codepad.org/idXxR5iA
抑或是:
利用動態2維陣列再quicksort
http://codepad.org/Y34tidcs
都在第 6 點 TLE ， 另我十分苦惱。

是否有大大能指點一下迷津，我不是相關科系畢業的，

所以寫出來的東西會有點像是東拼西湊出來的請見諒。

補充說明：

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.116.241.169
→ loveme00835:http://en.wikipedia.org/wiki/Radix_sort
→ loveme00835:在台灣的用法直的明明就稱為「行」...
推 bibo9901:我用C++的sort()就過了 XD
→ loveme00835:後來發現他的基底非常多, radix sort 行不通, 概念是
→ loveme00835:相同的, 第一次排序只比較最後一列的數字, 第二次只
→ loveme00835:比較倒數第二列的數字, 依此類推...但是這又要考慮排
→ loveme00835:序法的穩定性 : http://tinyurl.com/2785anl , 可以考
→ loveme00835:慮把快速排序成其他排序法, 像是合併排序、插入排序等
→ loveme00835:回 bibo9901 大, 您應該是在每兩列的紀錄比較時, 是逐
→ loveme00835:行比較的關係吧?
推 loveme00835:建議原po可以把每一列的資料包成一個物件, 或是直接用
→ loveme00835:vector 來存, 然後在 swap 的時候改成「換指標」即可
stl的東西我都沒學過不知道該如何使用，love大能分享一下作法嗎? 感恩..
我把quicksort中的swap改成指標互換就AC了，真是一語點醒夢中人
推 Fenikso:關鍵根本在要用scanf讀input..
推 Fenikso:不需要指標, vector交換並不會慢多少
→ loveme00835:是喔 XD
→ loveme00835:測試結果 : vector交換還是TLE Q_Q
→ bleed1979:這題橫列排序比直行排序快個10來ms。
※ 編輯: unfun           來自: 60.250.238.157       (07/02 09:27)
→ loveme00835:用你原本的方法會比較快 ~ " ~
→ loveme00835:全用C++標準庫好像很難AC ...
→ unfun:有沒有大大能幫我把樹改成能AC的樹
→ loveme00835:普通的BST會遇上歪斜樹的情況, 運算量會很龐大
推 cutecpu:http://codepad.org/uBEyfFD5 <= 單純用 C qsort 寫的
→ cutecpu:能 AC 但速度沒有很快
→ bleed1979:指標的指標，動態malloc會快一些。
→ bleed1979:到最後會發現方法都差不了多少，全讀字元轉整數最快了。
→ horngsh:你在用cin or cout時系統丟出例外,.
→ horngsh:請忽略樓上...pcman 秀逗了.