d660 - 11764 - Jumping Mario
題目描述
題目要求計算瑪莉歐跳躍過程中，向上跳（跳到較高的牆）和向下跳（跳到較矮的牆）的次數。給定一串牆壁的高度，瑪莉歐從第一個牆開始，依序跳到相鄰的牆，直到最後一個牆。
解題思路
這題的解題思路非常直接。我們只需要遍歷牆壁高度的陣列，比較相鄰兩個牆的高度，如果後一個牆比前一個牆高，則向上跳的次數加一；如果後一個牆比前一個牆矮，則向下跳的次數加一。對於每組測試案例，初始化向上跳和向下跳的計數器為零，然後進行比較。
複雜度分析
- 時間複雜度: O(n^2)，其中 n 是牆壁的數量。外層迴圈遍歷測試案例，內層迴圈遍歷每個案例中的牆壁。
- 空間複雜度: O(1)，因為我們只使用了幾個整數變數來儲存計數器和輸入值，空間使用量不隨輸入大小變化。
程式碼
#include <iostream>
using namespace std;
int main(){
int n=0,b=0,c=0,d=0;
int high=0,low=0;
while(cin >> n){
for(int i=1;i<=n;i++){
cin >> b;
for(int j=1;j<=b;j++){
d=c;
cin >> c;
if(j!=1){
if(c>d){
high++;
}
else if(c<d){
low++;
}
}
}
cout << "Case " << i << ": " << high << " " << low << endl;
high=0;
low=0;
}
}
}