ZeroJudge O076: 特技表演

有一個城鎮有 N 棟高樓,樓高分別為 H1、H2、…、HN,市長想要在城鎮中心舉辦高空特技表演,該特技表演會從某棟大樓上朝右側滑翔至地面。

為了表演人員的安全,滑翔的路徑樓高必須越來越低,請你找出一個最長的滑翔路徑

範例測資

範例輸入範例輸出
第一行有一個正整數 N (5 <= N <= 100)。
第二行有 N 個正整數 H1、H2、…、HN (1 <= Hi <= 1000)代表樓高。
輸出最長的滑翔路徑長度。
5
6 2 5 3 1
3
10
31 41 97 93 23 89 59 26 15 58
4

解題思路

收資料的時候將數字都收到一個陣列中,如果目前收到的數字非第一個數字則和陣列中前面的數值比大小。宣告一個 len 變數來存「目前遞減子區間長度」,還有一個 max 變數來存「最長遞減子區間長度」。

如果目前收到的數字比上一個數字還要小,則 len++。否則將 len = 1。每一次做這個判斷時都要和 max 做比較,如果 len > max 則 max = len。最後輸出 max 即可。

範例程式碼-ZeroJudge O076: 特技表演

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

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

//ZeroJudge O076
//Dr. SeanXD

發佈留言