c199 - 爬山去(Hiking)-TOI練習賽y7m5-1

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算給定高度序列中，有多少個高度比其前後高度都高的點，這些點被視為山頭。需要注意的是，序列的第一個和最後一個高度不考慮為山頭，且高原（連續相同高度）也算作山頭。

解題思路

程式碼首先讀取輸入的高度序列。然後，它建立一個新的序列 c，其中只包含高度發生改變的點。這樣可以有效地去除連續相同高度，簡化後續的山頭判斷。最後，程式碼遍歷 c 序列，檢查每個點是否比其前後的點都高。如果是，則將山頭計數器 ans 增加 1。

複雜度分析

• 時間複雜度: O(n)，其中 n 是輸入的高度序列的長度。程式碼需要遍歷輸入序列兩次，一次用於建立簡化序列 c，另一次用於計算山頭數量。
• 空間複雜度: O(n)，在最壞情況下，簡化序列 c 的大小可能與輸入序列相同（例如，輸入序列中沒有連續相同的高度）。

程式碼

#include <iostream>
using namespace std;
int main(){
	int a;
	while(cin >> a){
		int b[a],ans=0,c[a]={0},h=0;
		for(int i=0;i<a;i++){
			cin >> b[i];
		}
		for(int i=0;i<a;i++){
			if(b[i]!=b[i+1]){
				c[h]=b[i];
				h++;
			}
		}
		for(int i=1;i<h-1;i++){
			if(c[i]>c[i+1]&&c[i]>c[i-1]){
				ans++;
			}
		}
		cout << ans << "\n";
	}
}