b966 - 3. 線段覆蓋長度

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算一維座標上多個線段所覆蓋的總長度，需要注意線段重疊的部分只計算一次。輸入包含線段的數量 N，以及 N 個線段的起始點 L 和結束點 R。輸出覆蓋的總長度。

解題思路

此題使用一個布林陣列 aa 來模擬座標軸。對於每個線段，將其覆蓋的每個座標點在 aa 陣列中標記為 true。最後，遍歷 aa 陣列，計算 true 的數量，即為覆蓋的總長度。這種方法簡單直接，但空間複雜度較高，因為需要一個很大的布林陣列來存儲所有可能的座標點。

複雜度分析

• 時間複雜度: O(N * M)，其中 N 是線段的數量，M 是座標軸的最大範圍 (10000000)。
• 空間複雜度: O(M)，其中 M 是座標軸的最大範圍 (10000000)。

程式碼

#include <iostream>
using namespace std;
bool aa[10000000]={0};
int main(){
	int a,sum=0;
	cin >> a;
	int b,c;
	while(a--){
		cin >> b >> c;
		for(int i=b;i<c;i++){
			aa[i]=1;
		}
	}
	for(int i=0;i<10000000;i++){
		sum+=aa[i]; 
	}
	cout << sum << "\n";
}