發表新討論
#23941: upper_bound ( C++ )


yes51851823@gmail.com (wseds)

學校 : 國立花蓮高級工業職業學校
編號 : 108813
來源 : [114.36.212.168]
最後登入時間 ：
2024-10-17 21:35:26
f581. 3. 圓環出口 -- 2020年7月APCS | From: [111.243.224.61] | 發表日期 : 2021-01-03 20:25

這題只有0.5秒且資料量也不小，如果採取模擬法很可能會TLE，所以用C++的人可以善用vector的upper_bound。

先建前綴和的表再用upper_bound即可快速找到每次任務的結束點（要注意回到原點的狀況），由於upper_bound是採用二分搜尋法而非線性搜尋，所以可以把每次求任務完成點的複雜度由O(N)降為O(log N)。

 
ZeroJudge Forum