#23941: upper_bound ( C++ )
yes51851823@gmail.com
(wseds)
學校
:
國立花蓮高級工業職業學校
編號 : 108813
來源 : [114.36.253.126]
最後登入時間 ：
2025-08-25 16:32:53
這題只有0.5秒且資料量也不小，如果採取模擬法很可能會TLE，所以用C++的人可以善用vector的upper_bound。
先建前綴和的表再用upper_bound即可快速找到每次任務的結束點（要注意回到原點的狀況），由於upper_bound是採用二分搜尋法而非線性搜尋，所以可以把每次求任務完成點的複雜度由O(N)降為O(log N)。