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


bigpig (Bigpig)

學校 : 國立大里高級中學
編號 : 18246
來源 : [36.231.117.224]
最後登入時間 ：
2022-08-25 07:57:07
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...)

學校 : 國立臺南第一高級中學
編號 : 19129
來源 : [140.114.89.50]
最後登入時間 ：
2024-03-21 20:46:52
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