#25960: 方法


fire5386 (fffelix)

School : No School
ID : 115822
IP address : [36.227.234.44]
Last Login :
2021-09-21 18:06:20
a146. Sliding Window -- POJ 2823 | From: [111.243.25.233] | Post Date : 2021-07-07 21:45

窗口的k可能會大於n,所以讀入k後把k設為min(n, k)就可以避免Segmentation Fault了

方法一:

這題的做法可以用C++的multiset實作,min就是*ms.begin(), max就是*ms.rbegin()

時間複雜度:O(nlog(n)) 因為每次insert的時間為log(n),執行n次

AC (1.7s, 37MB)

方法二:

用deque實作,詳細的說明google上面很多

時間複雜度:O(n) 只需掃過array一次,array長度為n

AC (0.7s, 6.5MB)

 

 
ZeroJudge Forum