切換
舊版
前往
大廳
主題

ZeroJudge - e576: 10020 - Minimal Coverage 解題心得

Not In My Back Yard | 2019-12-24 19:33:26 | 巴幣 0 | 人氣 414

題目連結:


題目大意:
給定一正整數 T ,代表有 T 筆測試資料。

每筆第一列為空白列,接著的第二列給定一正整數 M (1 ≦ M ≦ 5000),代表一區間[0, M]。

再接著有若干列(最多100000),每列給定兩整數 L 、 R (|L|、|R| ≦ 50000,當 L = R = 0 時代表測資的結尾),每列代表一線段可覆蓋的區間[L, R]。

試問從給定的線段中,最少需要選出幾條線段才能使得這些線段覆蓋住區間[0, M]?如果全挑,無法使其覆蓋住[0, M],則輸出「0」;如果可以,請輸出最少的線段數,以及該挑那些線段。輸出格式請參見範例輸出。



範例輸入:
2

1
-1 0
-5 -3
2 5
0 0

1
-1 0
0 1
0 0


範例輸出:
0

1
0 1


解題思維:
把所有的線段先按照左端點由小到大排序,再依據右端點由小到大排。

接著用一變數 X 儲存現在已覆蓋的範圍之右端點。 X 的初始值為 0 ,代表一開始沒有任何線段覆蓋。接著掃過一次排序後的線段們,當碰到有線段的左端點 ≦ X ,代表該線段可以接上去;但是該條不一定是最佳的,因此繼續往後直到找到一條線段,其左端點盡可能接近 X (但是不超過 X)、右端點盡可能地遠。

當找到一條這樣的線段後,就將 X 更新為該線段的右端點之值。然後繼續著以上的動作,直到 X ≧ M ,或是已經沒有線段的左端點 ≦ X (代表已經接不下去)。

上述的動作跑完之後,判斷是否 X < M 。如果是,則代表這些線段無法覆蓋[0, M],因此輸出「-1」;反之,輸出挑的線段數以及那些該挑的線段(可以在過程中紀錄)。

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

創作回應

更多創作