CPE 一顆星
題目連結:https://zerojudge.tw/ShowProblem?problemid=d424
內容
所有的建築物都是矩形的，並且都建築在同一個平面上。
給定多棟建築物數據，求出這些建築物的空中輪廓(skyline)。
每列有一棟建築物資料，包含左邊位置 Li 、高度 Hi 、右邊位置 Ri。
所有數字都小於 10000，建築物已按照 Li 排列。
範例輸入
1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28
範例輸出
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0
想法
使用一個陣列紀錄該點最大建築物高度，一次讀取一棟建築物，若高於先前建築物，則更新。並紀錄最後一棟建築物的右邊位置。
接著遍歷陣列，若相鄰點高度不同，則輸出位置與高度。
程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false), cin.tie(nullptr)
using namespace std;
int main(){
fastio;
int Li, Hi, Ri, high[10001], R = -50;
memset(high, 0, sizeof(high));
while(cin >> Li >> Hi >>Ri){
for(int i = Li; i < Ri; ++i){
high[i] = max(Hi, high[i]);
R = max(Ri, R);
}
}
for(int i = 0; i <= R; ++i){
if(high[i] != 0 && i == 0){
cout << "0 " << high[i] << " ";
}
else if(high[i] != high[i+1]){
cout << i+1 << " " << high[i+1] << " ";
}
}
return 0;
}
|