發表新討論
#15818: TLE 如何提高執行速度?


hshua (hshua)

學校 : 新北市立林口高級中學
編號 : 52506
來源 : [125.228.147.181]
最後登入時間 ：
2024-11-10 13:26:19
c421. pA 雲端列印 -- 104學年度全國資訊學科能力競賽 | From: [220.133.124.235] | 發表日期 : 2018-11-02 18:57

AC 81%

TLE 如何提高執行速度?

 
#15823: Re:TLE 如何提高執行速度?


314159265358979323846264338327 ... (少年π)

學校 : 臺北市私立延平高級中學
編號 : 69058
來源 : [223.136.179.30]
最後登入時間 ：
2024-04-29 19:11:35
c421. pA 雲端列印 -- 104學年度全國資訊學科能力競賽 | From: [223.140.57.234] | 發表日期 : 2018-11-03 08:44

AC 81%

TLE 如何提高執行速度?

I/O優化了嗎?
如果是演算法問題,沒程式碼也無法解釋

 

 
#15862: Re:TLE 如何提高執行速度?


rollfc (胖胖貓)

學校 : 國立清華大學
編號 : 81012
來源 : [49.216.18.187]
最後登入時間 ：
2024-11-10 10:25:04
c421. pA 雲端列印 -- 104學年度全國資訊學科能力競賽 | From: [140.113.208.181] | 發表日期 : 2018-11-04 10:23

AC 81%

TLE 如何提高執行速度?

I/O優化了嗎?
如果是演算法問題,沒程式碼也無法解釋

 



借討論串問一下

因為題目必須要像 dequeue 可以從前面和後面把數字移除，把數字插入合適的位置(讓數列保持由小到大)

我自己的做法是用vector模擬和二分搜尋決定插入的位置

但是這樣最糟的情況就是每次都要插入最前面導致不斷搬動後面的數字

實作結果是測資#26 會TLE

想問一下有哪種結構可以符合需求？

 

 
#15873: Re:TLE 如何提高執行速度?


OwO310659 (OwO)

學校 : 新北市立板橋高級中學
編號 : 58647
來源 : [118.150.111.60]
最後登入時間 ：
2024-04-25 01:16:40
c421. pA 雲端列印 -- 104學年度全國資訊學科能力競賽 | From: [106.105.27.148] | 發表日期 : 2018-11-04 18:29

本題可以使用 <multiset> ,  (類似<set>但可以儲存重複的數值)
這樣 插入、刪除、查詢最大(小) 的 時間複雜度 都是 O(lgN) ,
這樣就可以AC了~

另外也可以使用 2個 <priority_queue> 來實作,
雖然時間複雜度一樣但效率會更好唷~

以上希望有幫助到你~ OwO

 
#15896: Re:TLE 如何提高執行速度?


hshua (hshua)

學校 : 新北市立林口高級中學
編號 : 52506
來源 : [125.228.147.181]
最後登入時間 ：
2024-11-10 13:26:19
c421. pA 雲端列印 -- 104學年度全國資訊學科能力競賽 | From: [125.227.237.177] | 發表日期 : 2018-11-05 09:37

本題可以使用 ,  (類似但可以儲存重複的數值)
這樣 插入、刪除、查詢最大(小) 的 時間複雜度 都是 O(lgN) ,
這樣就可以AC了~

另外也可以使用 2個 來實作,
雖然時間複雜度一樣但效率會更好唷~

以上希望有幫助到你~ OwO


感謝

 
ZeroJudge Forum