#37581: 解題思路(含一些小技巧)


edoctopus322@gmail.com (Moon Jam)

學校 : 臺北市立成功高級中學
編號 : 167591
來源 : [36.225.19.60]
最後登入時間 :
2023-12-23 13:47:18
b966. 3. 線段覆蓋長度 -- 2016年3月apcs | From: [36.225.13.17] | 發表日期 : 2023-09-17 21:29

 
解題思路:
如果直接開個陣列記錄每格格子走過了沒,最後再去檢查,但時間複雜度會是O(NL)會到10^11次方(L代表座標範圍),肯定會TLE,改成用priority queue(Heap)去存輸入,讓左界是由小到大排列(或者一開始用陣列儲存之後再sort,時間複雜度一樣不變是 O(N log N) ),並紀錄目前右界最大值,就可以確定後續資料的左界不會比前面的小,並用result紀錄目前覆蓋的格子數,這樣只要判斷以下兩種狀況

1. 輸入的左界目前右界最大值還大:將result加上整段區間長度,並更新右界最大值為輸入的右界
2. 輸入的左界目前右界最大值小且輸入的右界也比前右界最大值大:將result加上輸入右界到目前最大值的範圍,並更新右界最大值為輸入的右界
(若輸入的左界目前右界最大值小且輸入的右界也比前右界最大值小,則目前這個區間都在目前已涵蓋的格子內)

而如此一來就可以讓時間複雜度小至O(N log N),能夠在題目給定時間內完成

🌟 可以搭配pair使用會比較方便
 
ZeroJudge Forum