ZeroJudge A813: 城市觀測

在高雄市的某街道上，有許多高矮不等的房子排成整齊的一列。

對於兩棟不同的房子 A 與 B 來說，如果房子 A 與房子 B 之間的所有其他房子高度，都同時不超過房子 A 與房子 B 的高度，則站在房子 A 上面的人可以看到房子 B。

ZeroJudge A813 題目解說

如上圖，由左至右共有五棟房子，其高度分別為 5、2、3、4、4。當我們站在最右邊的房子上，因為我們所在的房子高度為 4，與最左邊的房子 (高度 5) 之間的所有其他房子 (高度為 2、3、4) 都不超過所在的房子 (高度 4) 及最左邊的房子 (高度 5），故我們可以看到最左邊的房子。同理，我們也能看到右邊第二棟房子。

給你一條街道從左至右的所有房子高度，設有 N 棟房子，站在第 k 棟房子上面的人，所能看見的其他房子總數為 Ck，則請計算 C1+C2 +⋯+CN 的總和是多少？

範例測資

範例輸入範例輸出
測試資料的輸入只有兩列。
第一列為一個正整數 N，表示該街道共有 N 棟房子。
第二列為 N 個正整數 (H1, H2, .…，HN），表示從左至右每一棟房子的高度。
請輸出一列，其中包含一個整數，表示請問每一棟房子所能看見的其他房子數
量總和是多少，也即 C1+C2+⋯+CN。
2
1 1		2
3
1 2 3		4
5
5 2 3 4 4		14
ZeroJudge A813 範例測資

解題思路

本題需要使用 Long Long Int 來存資料。

宣告一個 pair<long long int, long long int> 的陣列，這個會是一個暫存區，從左到右和右到左看的原理是一樣的，以下這個暫存區簡稱為 Box。

每一次跑到一棟樓時，都要判斷 Box 裡面是否有資料，如果沒有資料就將目前的樓高度 push_back 到 Box 中，因為陣列的資料型態是 Pair，First 欄位是存樓高度，Second 欄位是存連續的時候這個高度有連續幾個。如果裡面已經有資料了就要跑一個 While 迴圈，每一次的迴圈裡要鎖定 Box 的最後一個資料，簡稱 Last。如果 Last 大於目前樓高度，就代表已經不能往前了，將 ans++ 之後就將 While 迴圈 Break 掉。如果 Last 小於目前樓高度，則將 ans += Last.second，也就是有幾個這個高度的樓棟，並且將 Box 做 pop_back。如果 Last 等於目前樓高度，則要先將 ans += Last.second，然後才將 Last.second++。並且如果 Box 中還有其他的資料就將 ans++。如果是等於的情況就不需要將目前樓高度做 push_back，其餘情況都要 push_back。

範例程式碼－ZeroJudge A813: 城市觀測

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

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    vector<long long int>building;
    vector<pair<long long int, long long int>>box;
    cin >> N;
    long long int ans = 0;
    for (int i = 0; i<N; i++) {
        int tmp;
        cin >> tmp;
        building.push_back(tmp);
        if (box.empty()) {
            box.push_back(make_pair(tmp, 1));
        }
        else {
            long long int count = 0;
            bool push = true;
            while (true) {
                const int last = box.size()-1;
                if (box.empty()) break;
                if (box[last].first > tmp) {
                    count++;
                    break;
                }
                if (box[last].first == tmp) {
                    count += min(1, int(box.size()-1));
                    count += box[last].second;
                    box[last].second++;
                    push = false;
                    break;
                }
                if (box[last].first < tmp) {
                    count += box[last].second;
                    box.pop_back();
                }
            }
            if (push) box.push_back(make_pair(tmp, 1));
            ans += count;
        }
    }
    box.clear();
    for (int i = N-1; i>=0; i--) {
        const int tmp = building[i];
        if (box.empty()) {
            box.push_back(make_pair(tmp, 1));
        }
        else {
            long long int count = 0;
            bool push = true;
            while (true) {
                const int last = box.size()-1;
                if (box.empty()) break;
                if (box[last].first > tmp) {
                    count++;
                    break;
                }
                if (box[last].first == tmp) {
                    count += box[last].second;
                    count += min(1, int(box.size()-1));
                    box[last].second++;
                    push = false;
                    break;
                }
                if (box[last].first < tmp) {
                    count += box[last].second;
                    box.pop_back();
                }
            }
            if (push) box.push_back(make_pair(tmp, 1));
            ans += count;
        }
    }
    cout << ans << "\n";
}

//ZeroJudge A813
//Dr. SeanXD
標籤

相關文章

發佈留言