ZeroJudge G595: 修補圍籬

有一個農場有寬度為 N 的圍籬，每個圍籬都有各自的高度 H1～HN。

有些圍籬被吹斷了，農場主人要來修補這些圍籬，但他忘記這些壞掉的圍籬原本高度是多少，為了減少成本，他會取斷掉的圍籬位置相鄰左邊和右邊較小的那個高度填上去，問需要多少成本

題目保證不會有兩個相鄰的吹斷圍籬，而穿斷的圍籬有可能位在邊界。

範例測資

範例輸入範例輸出
輸入包含兩行
第一行有一個正整數 N
第二行有 N 個以空隔分隔的整數 H1～HN		輸出一個正整數表示新增的圍籬長度總和
3
2 0 4		2
9
0 5 3 0 6 4 0 1 0		10

解題思路

將柵欄的高度存到一個陣列裡，並且跑一個 For迴圈 從 0 到 N-1。如果 H[i] 是 0 的話就要判斷左右兩邊哪邊比較低並加到答案裡。

如果目前的 i 是位於邊界 (0 或是 N-1)，不需要判斷大小直接把另外一邊的柵欄長度加到答案裡。

範例程式碼－ZeroJudge G595: 修補圍籬

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

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, ans = 0;
    cin >> N;
    vector<int>num;
    for (int i = 0; i<N; i++)
    {
        int tmp;
        cin >> tmp;
        num.push_back(tmp);
    }
    for (int i = 0; i<N; i++)
    {
        if (num[i] == 0)
        {
            if (i == 0)
            {
                ans += num[i+1];
                continue;
            }
            if (i == N-1)
            {
                ans += num[i-1];
                continue;
            }
            ans += min(num[i+1], num[i-1]);
        }
    }
    cout << ans << "\n";
}

//ZeroJudge G595
//Dr. SeanXD
標籤

相關文章

發佈留言