105 - The Skyline Problem

出處: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=41

---

問題敘述

此問題會輸入很多組長方形建築物的資料，每組資料分別是: 左x座標, 高度, 右x座標，輸入資料會照著左x座標由小到大排序，得到所有建築物的資料之後，必須輸出"天際線向量"。所謂天際線向量，就是用一個長的像這樣子的向量: (v1, v2, v3, ... , vn) 來表示天際線，奇數位置填的是x座標，偶數位置填的是高度，必須從最小的x座標開始填起。

解題思路

這題有一個可以減少我們很多功夫的關鍵點，那就是所有座標都是小於10,000的整數，也就是說我們只要開一個10,000個元素的陣列，暴力記下每一個x座標的最高點，就可以完成天際線向量了。所以此題的演算法大致上是如此: 每讀入一組建築物資料，就更新那一區塊的所有x座標的最高點(注意不要更新到建築物最右邊座標的高度，因為這樣才能知道哪個x座標開始產生高度變化)，最後只要從小到大把每個x座標的最高點掃描一遍，就可以印出天際線向量了。

c++ 程式碼

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int left, right, height, last;
    int first = -1;
    int nowHeight = 0;
    vector<int> heightVec(10000, 0);

    while (cin >> left >> height >> right) {
        if (first == -1) {
            first = left;
            last = right;
        }
        if (right > last)
            last = right;
        for (int i=left; i<right; i++) {
            if (height > heightVec[i])
                heightVec[i] = height;
        }
    }
    for (int i=first; i<=last; i++) {
        if (heightVec[i] != nowHeight) {
            cout << i << " " << heightVec[i];
            if (i == last)
                cout << endl;
            else {
                cout << " ";
                nowHeight = heightVec[i];
            }
        }
    }

    return 0;
}