ZeroJudge o076 題解

特技表演

原 APCS 2024年 6月 第一題

題目敘述

有一個城鎮有 n 棟高樓，樓高分別為 h1, h2, h3 ~ hn，市長想要在城鎮中心舉辦高空特技表演，該特技表演會從某棟大樓上 朝右側 滑翔至地面。

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

解題思路

題目要你做的事情就是，找一個起點，從那個起點開始滑翔，可以飛越最多高樓而不撞上高樓。

Step 1.
存入 n 個樓高 h

int n; // 初始化 n
cin >> n; // 輸入 n
int h[n]; // 初始化一個長度為 n 的陣列 h

for (int i = 0; i < n; i++) {
    cin >> h[i]; // 從陣列 h 的最左邊[0] 輸入到最右邊[n-1]
}

Step 2.
以每棟建築物為起點，試著飛飛看，計算每個棟建築物最多可以飛越幾棟右方的建築

for (int i = 0; i < n; i++) { // 從最左邊試到最右邊
    int now = h[i]; // 變數 now 的意思是現在位置的建築物高度
    int cnt = 1; // 變數 cnt 紀錄可以飛越幾棟建築物，初始是 1 (腳下這棟建築物已經算飛過了)
    
    for (int j = i + 1; j < n; j++) { // 每次從起點往右飛到底
        if (h[j] < now) { // h[j] 是正準備飛過的下一棟建築
            cnt++;
            now = h[j];
        } else {
            break; // 飛不過去，結束起點 i 的測試
        }
    }
}

Step 3.
維護一個最大值 k 也就是最遠可以飛幾棟建築
以 Step 2 的程式為基礎，加入可以維護最大值的判斷式

int k = 1; // 初始化最大值 k，因為最少最少，可以飛過1棟建築物，也就是腳下這棟

for (int i = 0; i < n; i++) { // 從最左邊試到最右邊
    int now = h[i]; // 變數 now 的意思是現在位置的建築物高度
    int cnt = 1; // 變數 cnt 紀錄可以飛越幾棟建築物，初始值是 1 (腳下這棟建築物已經算飛過了)
    
    for (int j = i + 1; j < n; j++) { // 每次從起點往右飛到底
        if (h[j] < now) { // h[j] 是正準備飛過的下一棟建築
            cnt++;
            now = h[j];
        } else {
            break; // 飛不過去，結束起點 i 的測試
        }
    }
    
    if (cnt > k) { // 如果這次測試飛越的建築物數量超過 k
        k = cnt; // 將 k 設定為這次的 cnt
    }
}

Step 4.
合併以上程式，輸出答案
以下是可以通過的程式

#include <iostream>
using namespace std;

int main() {
    int n; 
    cin >> n;
    int h[n]; 

    for (int i = 0; i < n; i++) {
        cin >> h[i];

    }
    
    int k = 1;

    for (int i = 0; i < n; i++) { 
        int now = h[i];
        int cnt = 1;
    
        for (int j = i + 1; j < n; j++) { 
            if (h[j] < now) { 
                cnt++;
                now = h[j];
            } else {
                break; 
            }
        }
    
        if (cnt > k) { 
            k = cnt;
        }
    }
    
    cout << k; // 輸出答案
}