發表新討論
#8039: 如何加速


bigpig (Bigpig)

d401. B-成績單 -- 板橋高中98-2模擬測驗 | From: [123.240.30.168] | 發表日期: 2013-08-04 07:41

我用了Vector + sort AC

但是花了0.9s

要加速是否要自己搞一個資料結構 

#8042: Re:如何加速


lfs92002 (GMan每日殺水題1.6449340668482264364...)

d401. B-成績單 -- 板橋高中98-2模擬測驗 | From: [140.114.87.231] | 發表日期: 2013-08-04 16:48

我用了Vector + sort AC

但是花了0.9s

要加速是否要自己搞一個資料結構 


不用全部排序，用Quick Sort的想法，選擇一數字 A，將比A小的數放到A的左邊，比A大的數字放到右邊，則最後可以確定A是第幾大的數字，再依題目所求向左或右遞迴到所求，時間複雜度理想為O(n)，比排序的O(nlogn)來的快
ZeroJudge Forum