ZeroJudge F072: 家裡的後花園 (Garden)

小明搬到一個新家，新家跟舊家很不一樣的地方就是新家的後方多了一大塊花圃，小明決定要幫他的花圃放上一些柵欄以及種上一些花。為了美觀性質，小明決定只在柵欄與柵欄之間的空地種花。但是事情沒有這麼容易，小明發現某些位置會出現害蟲，當某一塊地出現害蟲時，那一塊地與左右相鄰的兩塊地皆無法種花。

小明決定用數字紀錄花圃的情況，數字 0 代表一塊空地，數字 1 代表該地放置柵欄，數字 9 代表的是該地有害蟲。小明想要計算他最多可以種下幾朵花，好讓他去花店買種子來種。

範例測資

範例輸入範例輸出
第一行有一個整數 N (1 ≤ N ≤ 25），代表小明的花圃有幾塊地 (花園形狀為一直線），接著第二行會帶有 N 個數字，只會出現 0 或 1 或 9 三個數字。請輸出小明最多可以種下多少花。
5
1 0 0 0 1		3
10
0 1 0 1 0 1 0 0 1 0		4
13
0 1 0 9 1 0 1 0 9 0 0 1 0		2

解題思路

設定一個 count 變數預設為 0，代表有沒有遇到柵欄了，並且預設一個 zero 代表 0 出現的次數。如果今天遇到 0 了但是 count 為 1，代表沒有柵欄所以這裡的 0 都不算。如果遇到柵欄時就將 count 變成 1，當 count 是 1 時，花的數量就可以被記錄在 zero 中。每次遇到柵欄時，就將目前的 zero 加到答案中，並且將 zero 歸零。

當遇到花時需要判斷前後是否有害蟲，如果有的話就不能將 zero++。判斷時需要注意第一個和最後一個位置只需要判斷一遍是否有害蟲避免造成記憶體區段錯誤。

範例程式碼－ZeroJudge F072: 家裡的後花園 (Garden)

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

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, count = 0, zero = 0, 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 (count == 0) continue;
            if (i == 0) {
                if (num[i+1] != 9) zero++;
                continue;
            }
            if (i == N-1) {
                if (num[i-1] != 9) zero++;
                continue;
            }
            if (num[i+1] != 9 && num[i-1] != 9) zero++;
            continue;
        }
        if (num[i] == 1) {
            count++;
            ans += zero;
            zero = 0;
        }
    }
    cout << ans << "\n";
}

//ZeroJudge F072
//Dr. SeanXD
標籤

相關文章

發佈留言