b139 - NOIP2005 2.校门外的树

🔗 前往 ZeroJudge 原題

題目描述

題目描述了在一段長度為 L 的馬路上，有 M 個需要移除樹木的區域。給定每個區域的起始點和終止點，要求計算移除樹木後，馬路上剩餘的樹木數量。

解題思路

此題的核心思路是使用一個布林陣列 b 來模擬馬路上的樹木。陣列的索引代表馬路上的位置，b[i] = 1 表示位置 i 的樹木需要被移除，b[i] = 0 表示位置 i 的樹木保留。

程式首先讀取馬路的長度 a 和區域的數量 m。然後，對於每個區域，讀取其起始點 d 和終止點 u。如果 d 大於 u，則交換它們以確保 d 始終是起始點，u 始終是終止點。接著，將從 d 到 u (包含 d 和 u) 的所有位置的對應 b 陣列元素設為 1，表示這些位置的樹木需要被移除。

最後，遍歷 b 陣列，計算 b[i] == 0 的數量，即剩餘的樹木數量，並輸出結果。

複雜度分析

• 時間複雜度: O(L * M)
• 空間複雜度: O(L)

程式碼

#include <iostream>
using namespace std;
int main(){
	int a,m;
	while(cin >> a >> m){
		int b[a+1]={0},d,u,sum=0;
		for(int i=0;i<m;i++){
			cin >> d >> u;
			if(d>u){
				d=d^u;
				u=d^u;
				d=d^u;
			}
			for(int j=d;j<=u;j++){
				b[j]=1;
			}
		}
		for(int i=0;i<=a;i++){
			if(b[i]==0){
				sum++;
			}
		}
		cout << sum << "\n";
	} 
}