<style> .markdown-body table{ display: unset; } </style> # APCS實作題2016年3月第3題：線段覆蓋長度 > 第1版：2023年2月8日 > 第2版：2023年10月19日 > 第3版：2024年12月4日，讀了吳邦一教授的 AP325 講義之後重寫程式碼 > 作者：王一哲 > 題目來源：[105年3月5日實作題第3題](https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2020/10/APCS-%E5%AF%A6%E4%BD%9C%E9%A1%8C-2016.03.05.pdf) > [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=b966) <br /> ## 題目 ### 問題描述 給定一維座標上一些線段，求這些線段所覆蓋的長度，注意，重疊的部分只能算一 次。例如給定四個線段，(5, 6)、(1, 2)、(4, 8)、和(7, 9)。如下圖，線段覆蓋長度為 6。 <img height="80%" width="80%" src="https://i.imgur.com/ehcyKZl.png" style="display: block; margin-left: auto; margin-right: auto;"/> <br /> ### 輸入格式 第一列是一個正整數 N，表示此測試案例有 N 個線段。 接著的 N 列每一列是一個線段的開始端點座標和結束端點座標整數值，開始端點座標值小於等於結束端點座標值，兩者之間以一個空格區隔。 <br /> ### 輸出格式 輸出其總覆蓋的長度。 <br /> ### 範例一：輸入 <center> | 輸入 | 說明 | | --- | --- | | 5 | 此組測試案例有 5 個線段 | | 160 180 | 開始端點座標值與結束端點座標 | | 150 200 | 開始端點座標值與結束端點座標 | | 280 300 | 開始端點座標值與結束端點座標 | | 300 330 | 開始端點座標值與結束端點座標 | | 190 210 | 開始端點座標值與結束端點座標 | </center> ### 範例一：正確輸出 <center> | 輸入 | 說明 | | --- | --- | | 110 | 測試案例的結果 | </center> <br /> ### 範例二：輸入 <center> | 輸入 | 說明 | | --- | --- | | 1 | 此組測試案例有 1 個線段 | | 120 120 | 開始端點座標值與結束端點座標 | </center> ### 範例二：正確輸出 <center> | 輸入 | 說明 | | --- | --- | | 0 | 測試案例的結果 | </center> <br /> ### 評分說明 輸入包含若干筆測試資料，每一筆測試資料的執行時間限制(time limit)均為 2 秒，依正確通過測資筆數給分。每一個端點座標是一個介於 0~M 之間的整數，每組測試案例線段個數上限為 N。其中： - 第一子題組 30 分，M<1000，N<100，線段沒有重疊。 - 第二子題組 40 分，M<1000，N<100，線段可能重疊。 - 第三子題組 30 分，M<10000000，N<10000，線段可能重疊。 <br /> ## Python 程式碼 ### 寫法1，依照左端點由小到大排序 花費時間最久為 78 ms，使用記憶體最多為 4.8 MB，通過測試。 ```python= N = int(input()) # 線段數量 segs = sorted([tuple(map(int, input().split())) for _ in range(N)]) # 讀取線段端點，依照左端點由小到大排序 now = [-1, -1] # 目前所在線段左、右端點，預設為 -1，因為題目的端點最小值為 0 ans = 0 # 答案，線段覆蓋長度 for le, ri in segs: # 依序讀取線段左、右端點 if le > now[1]: # le 在目前線段右端點右側，新的線段 ans += now[1] - now[0] # 將目前線段長度加到 ans now = [le, ri] # 更新目前線段端點 else: # le 在目前線段左、右端點之間，線段合併 now[1] = max(now[1], ri) # 更新右端點，選較大的值 # end of for loop ans += now[1] - now[0] # 要加上最後一段的長度 print(ans) ``` <br /><br /> ### 寫法2，計算重疊線段厚度 花費時間最久為 85 ms，使用記憶體最多為 5.5 MB，通過測試。 ```python= N = int(input()) # 線段數量 segs = [] # 線段端點，左端點厚度加1，右端點厚度減1，依照端點由小到大排序 for _ in range(N): le, ri = map(int, input().split()) segs += [(le, 1), (ri, -1)] segs.sort() now = -1 # 目前的端點，預設為 -1，因為題目的端點最小值為 0 thick = 0 # 覆蓋厚度 ans = 0 # 答案，線段覆蓋長度 for p, t in segs: # 依序讀取端點及厚度變化 if thick == 0: now = p # 如果目前的厚度是零，p 為新的線段起點 thick += t # 更新厚度 if thick == 0: ans += p - now # 厚度歸零，沒有任何線段覆蓋此點，更新答案 # end of for loop print(ans) ``` <br /><br /> ## C++ 程式碼 ### 寫法1，依照左端點由小到大排序 花費時間最久為 7 ms，使用記憶體最多為 416 kB，通過測試。 ```cpp= #include <iostream> #include <vector> #include <utility> #include <algorithm> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int N; cin >> N; // 線段數量 vector<pair<int, int>> segs (N); // 線段端點，依照左端點由小到大排序 for(int i=0; i<N; i++) cin >> segs[i].first >> segs[i].second; sort(segs.begin(), segs.end()); pair<int, int> now = make_pair(-1, -1); // 目前的端點，預設為 -1，因為題目的端點最小值為 0 int ans = 0; // 答案 for(auto seg : segs) { // 依序讀取線段左、右端點 if (seg.first > now.second) { // seg.first 在目前線段右端點右側，新的線段 ans += now.second - now.first; // 將目前線段長度加到 ans now = seg; // 更新目前線段端點 } else { // seg.first 在目前線段左、右端點之間，線段合併 now.second = max(now.second, seg.second); // 更新右端點，選較大的值 } } ans += now.second - now.first; // 要加上最後一段的長度 cout << ans << "\n"; return 0; } ``` <br /><br /> ### 寫法2，計算重疊線段厚度 花費時間最久為 7 ms，使用記憶體最多為 752 kB，通過測試。 ```cpp= #include <iostream> #include <vector> #include <utility> #include <algorithm> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int N; cin >> N; // 線段數量 vector<pair<int, int>> segs; // 線段端點，左端點厚度加1，右端點厚度減1，依照端點由小到大排序 for(int i=0, le, ri; i<N; i++) { cin >> le >> ri; segs.push_back(make_pair(le, 1)); segs.push_back(make_pair(ri, -1)); } sort(segs.begin(), segs.end()); int now = -1, thick = 0, ans = 0; // 目前的端點，預設為 -1，因為題目的端點最小值為 0；覆蓋厚度；答案 for(auto seg : segs) { // 依序讀取端點及厚度變化 if (thick == 0) now = seg.first; // 如果目前的厚度是零，seg.first 為新的線段起點 thick += seg.second; // 更新厚度 if (thick == 0) ans += seg.first - now; // 厚度歸零，沒有任何線段覆蓋此點，更新答案 } cout << ans << "\n"; return 0; } ``` <br /><br /> --- ###### tags:`APCS`、`Python`、`C++`