解題觀念
Greedy - 區間最小覆蓋
可以參考我的課程簡報：Greedy & Graph
題目敘述
給定多組線段座標 [Li, Ri] (在 x 軸上)
請選擇以最少數量的線段,使得選擇的線段完全覆蓋 [0, M]
輸入的第一行有一整數 t,表示測茲的數量
接下來每組測資的第一行為空白行
第二行為一整數 M
表示需覆蓋的線段最右值 (1 <= M <= 5000)
接下來有多行
每行有兩個整數 Li、Ri
表示可用線段的最左值及最右值
(|Li|、|Ri| <= 50000,i <= 100000)
若 Li == Ri == 0 則此組測資結束
1
2
3
4
5
6
7
8
9
10
11
12
| 2
1
-1 0
-5 -3
2 5
0 0
1
-1 0
0 1
0 0
|
Output
每組測資輸出
第一行輸出最少須選擇多少線段以覆蓋 [0, M]
接下來多行輸出選擇的線段座標
(依據 Li 由小到大排序)
如果所有可用線段無法使 [0, M] 被完全覆蓋則輸出 “0”
每組輸出之間需相隔一行
解題觀念簡報參考
STL - Vector
Greedy - 區間最小覆蓋
Solution Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include<bits/stdc++.h>
using namespace std;
struct Node{
int lef, rig;
bool operator < (const Node &rhs) const{
if(lef == rhs.lef) return rig > rhs.rig;
else return lef < rhs.lef;
}
};
int main(){
int t;
cin >> t;
bool space = false;
while(t--){
if(space) cout << endl;
space = true;
int M;
cin >> M;
vector<Node> seg;
int lef, rig;
while(cin >> lef >> rig && (lef || rig)){
seg.push_back({lef, rig});
}
sort(seg.begin(), seg.end());
int ptrLef = 0, ptrRig = -1;
vector<pair<int, int>> ans;
while(ptrRig < M){
int tmpLef = -50001;
for(int j = 0; seg[j].lef <= ptrLef && j < seg.size(); ++j){
if(seg[j].rig > ptrRig){
ptrRig = seg[j].rig;
tmpLef = seg[j].lef;
}
}
if(tmpLef == -50001) break;
ans.push_back({tmpLef, ptrRig});
ptrLef = ptrRig;
}
if(ptrRig >= M){
cout << ans.size() << endl;
for(int j = 0; j < ans.size(); ++j){
cout << ans[j].first << " " << ans[j].second << endl;
}
}
else cout << "0" << endl;
seg.clear();
ans.clear();
}
}
|
