d424 - 00105 - The Skyline Problem

🔗 前往 ZeroJudge 原題

題目描述

題目要求根據給定的建築物位置資訊，計算出這些建築物構成的天際線。建築物以 (Li, Hi, Ri) 的形式表示，其中 Li 和 Ri 分別是建築物的左邊和右邊位置，Hi 是建築物的高度。輸出天際線的座標序列，序列中奇數位置表示 x 座標，偶數位置表示高度，最後一個數必須為 0。

解題思路

程式碼使用一個陣列 a 來模擬整個城市的高度。對於每棟建築物，程式碼遍歷其左右位置之間的區間，如果建築物的高度大於當前位置的高度，則更新該位置的高度。最後，程式碼遍歷整個高度陣列，找出高度發生的變化點，並將這些變化點的 x 座標和高度輸出。程式碼利用貪心策略，每次只考慮當前建築物對天際線的影響，並逐步構建天際線。

複雜度分析

• 時間複雜度: O(N * M + M)，其中 N 是建築物的數量，M 是座標的最大值。遍歷所有建築物需要 O(N * M) 的時間，遍歷高度陣列需要 O(M) 的時間。
• 空間複雜度: O(M)，用於儲存高度陣列。

程式碼

#include <iostream>
using namespace std;
int a[10001]={0};
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	int x,y,z,n=0;
	bool t=0;
	while(cin >> x >> y >> z)
		for(int i=x;i<z;i++)
			if(y>a[i])
				a[i]=y;
	for(int i=0;i<=10000;i++){
		if(a[i]!=n){
			if(t==0){
				cout << i << " " << a[i] ;
				t=1;
			}
			else
				cout << " " << i << " " << a[i] ;
			n=a[i];
		}
	}
	cout << "\n";
}