b966: 第 3 題 線段覆蓋長度
標籤 : APCS
通過比率 : 68% (216 人 / 320 人 ) (非即時)
評分方式:
Strictly

最近更新 : 2018-07-30 16:24

內容

給定一維座標上一些線段,求這些線段所覆蓋的長度,注意,重疊的部分只能算一次。

例如給定 4 個線段:(5, 6)、(1, 2)、(4, 8)、(7, 9),如下圖,線段覆蓋長度為 6 。

輸入說明

輸入包含多筆測資。

每筆側資中,
第一列是一個正整數 ,表示此測資有 N 個線段。
接著的 N 列每一列是一個線段的開始端點座標整數值 L 和結束端點座標整數值 R ,開始端點座標值小於等於結束端點座標值,兩者之間以一個空格區隔。

 

其中  30%的測資滿足, N < 100 , 0 ≤ , R < 1000 ,並且線段沒有重疊。
其中  70%的測資滿足, N < 100 , 0 ≤ , R < 1000 ,並且線段可能重疊。
其中100%的測資滿足, N < 10000 , 0 ≤ , R < 10000000 ,並且線段可能重疊。

輸出說明

每筆測資輸出一行,輸出其總覆蓋的長度。

本題為嚴格比對,請務必按照說明進行輸出。

範例輸入
5
160 180
150 200
280 300
300 330
190 210
1
120 120
範例輸出
110
0
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (30%): 2.0s , <1M
公開 測資點#1 (40%): 2.0s , <1M
公開 測資點#2 (30%): 2.0s , <50M
提示 :

第一筆說明:覆蓋的範圍是 150~210 及 280~330 共長 110 。

第二筆說明:沒有覆蓋任何面積,故長度為 0 。

標籤:
APCS
出處:
APCS大學程式設計先修檢測(2016/03/05) [編輯:
snail (蝸牛)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」