ETH官方钱包

切換
舊版
前往
大廳
主題

ZeroJudge - b966: 第 3 題 線段覆蓋長度 解題心得

Not In My Back Yard | 2019-03-15 22:40:15 | 巴幣 2 | 人氣 957

題目連結:


題目大意:
第一列給定一正整數 N (N < 10, 000),代表接下來有N列輸入。每列輸入給定兩正整數 L 、 R (0 ≦ L 、 R < 10, 000, 000),代表有一個位於一標準數縣上之線段的左端點座標為 L 、右端點座標為 R 。

總和以上給定的線段,求這數線上有多少單位長度的區間被這些線段覆蓋著?



範例輸入:
5
160 180
150 200
280 300
300 330
190 210
1
120 120


範例輸出:
110
0


解題思維:
首先,我們將所有線段存在一個陣列裡(左右端點的座標可以用一個結構(Struct)或類別(Class)包起來)。然後,把線段們彼此先比較左端點的大小,小的排前面,大的排後面;如果一樣,再比右端點(也是小的排前,大的排後)。

因此陣列的最前面的元素即是左端點跟右端點都比其他線段小的線段,我們先將其當作第一個基準線。

接著,我們比較接下來的陣列中每一條線段之左端點是否 < 現在的基準線之右端點。如果是的話,則這條線就可以接在這條基準線後面,使得基準線變長;若非,則計算基準線的左端點和右端點的座標差,將此值加進答案裡。然後,令現在這條線作為新的基準線。

重複以上步驟直到所有線都判斷完之後,所有基準線之座標差的總和即是答案。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作