×
解除綁定,重新設定系統帳號的密碼
您的系統帳號 ID:
您的系統帳號:
您的帳號暱稱:
設定新密碼:
設定新密碼:
×
請輸入要加入的「課程代碼」
請向開設課程的使用者索取「課程代碼」
分類題庫
解題動態
排行榜
討論區
競賽區
登入
註冊
發表新討論
解題報告
#37582: 解題思路(含一些小技巧)
edoctopus322@gmail.com
(Moon Jam)
學校 : 臺北市立成功高級中學
編號 : 167591
×
傳送站內訊息
傳給:
主題:
內容:
來源 : [36.225.19.60]
最後登入時間 :
2023-12-23 13:47:18
f855.
第 3 題 線段覆蓋長度 測資加強版
--
APCS大學程式設計先修檢測
(2016/03/05)
| From: [36.225.13.17] | 發表日期 : 2023-09-17 21:29
完整題解:
https://moon-jam.me/zerojudge_b966_f855/
解題思路:
如果直接開個陣列記錄每格格子走過了沒,最後再去檢查,但時間複雜度會是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