e576 - 10020 - Minimal Coverage
題目描述
題目要求找出最少數量的線段，使得這些線段能夠完全覆蓋區間 [0, M]。給定一系列的線段，每個線段由其起始點 L 和結束點 R 定義。
解題思路
本題可以使用貪心演算法解決。首先，按照線段的起始點 L 進行排序。排序後，從左到右遍歷線段。
- 維護一個當前覆蓋到的最遠距離
st，初始值為 0。 - 維護一個當前線段的起始點
mit和結束點ma。 - 遍歷排序後的線段：
- 如果當前線段的起始點大於
st，則說明需要選擇一個新的線段來覆蓋從st到當前線段起始點之間的區間。將mit和ma記錄的線段作為一個覆蓋區間，更新st為ma，並繼續遍歷。 - 否則，如果當前線段的結束點大於
ma，則更新ma為當前線段的結束點，並更新mit為當前線段的起始點。
- 如果當前線段的起始點大於
- 遍歷完所有線段後，如果
st小於M，則說明無法完全覆蓋區間 [0, M]，輸出 0。否則，輸出選擇的線段數量。
複雜度分析
- 時間複雜度: O(n log n)，其中 n 是線段的數量。主要時間花費在排序上。
- 空間複雜度: O(n)，主要用於儲存線段和結果。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
struct p{
int l,r;
};
bool cmp(p x,p y){
if(x.l<y.l||(x.l==y.l&&x.r>y.r))return 1;
return 0;
}
int t,m,ans[100005][2];
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> t;
for(int ca=0;ca<t;++ca){
if(ca)cout << "\n";
cin >> m;
int it=0,x,y,ait=0,st=0,ma=0,mit=0,er=0;
p a[100005];
while(cin >> x >> y){
if(x==0&&y==0)break;
a[it].l=x;
a[it].r=y;
++it;
}
a[it].l=9999999;
a[it].r=9999999;
++it;
sort(a,a+it,cmp);
for(int i=0;i<it&&st<m&&er==0;++i){
if(a[i].l>st){
ans[ait][0]=mit;
ans[ait][1]=ma;
++ait;
st=ma;
if(st<a[i].l){
er=1;
}
--i;
}
else{
if(a[i].r>ma){
ma=a[i].r;
mit=a[i].l;
}
}
}
if(st<m){
cout << "0\n";
}
else{
cout << ait << "\n";
for(int i=0;i<ait;++i){
cout << ans[i][0] << " " << ans[i][1] << "\n";
}
}
}
}