f855 - 第 3 題 線段覆蓋長度 測資加強版
題目描述
題目要求計算一組線段在數軸上覆蓋的總長度。給定 N 個線段，每個線段由其左端點 L 和右端點 R 定義。線段可能重疊，題目要求計算所有線段覆蓋的總長度，避免重複計算重疊部分。
解題思路
本題可以使用貪心演算法解決。首先，按照線段的左端點升序排序。然後，遍歷排序後的線段，維護一個當前覆蓋區間的右端點 rit。對於每個線段，如果它的左端點大於或等於 rit，則表示它與當前覆蓋區間不重疊，將其加入覆蓋區間，並更新 rit。如果它的右端點大於 rit，則表示它與當前覆蓋區間部分重疊，將覆蓋區間的右端點更新為該線段的右端點。
複雜度分析
- 時間複雜度: O(N log N) (主要來自排序)
- 空間複雜度: O(N) (用於儲存線段)
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
struct p{
int l,r;
};p a[10001];
bool cmp(p x,p y){
if(x.l<y.l||(x.l==y.l&&x.r<y.r))return 1;
return 0;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n,sum=0,lit=0,rit=0;
cin >> n;
for(int i=0;i<n;++i)
cin >> a[i].l >> a[i].r;
sort(a,a+n,cmp);
for(int i=0;i<n;++i){
if(a[i].l>=rit){
lit=a[i].l;
rit=a[i].r;
sum+=rit-lit;
}
else if(a[i].r>rit){
sum+=a[i].r-rit;
rit=a[i].r;
}
}
cout << sum;
}