#40873: 神奇的做法C++


tudo.huang@gmail.com (Tudo Huang)

學校 : 不指定學校
編號 : 237944
來源 : [203.64.138.253]
最後登入時間 :
2024-06-14 14:35:48
o076. 1. 特技表演 -- 2024年6月APCS | From: [118.169.21.115] | 發表日期 : 2024-06-16 18:59

我們需要找到一個滑翔路徑,使得路徑上的樓高必須越來越低,並求出最長的滑翔路徑長度。

建立一個vector來記錄建築物的高度,另一個vector 來記錄從每棟建築開始滑翔的最長距離。

2. 計算滑翔距離- 使用兩個嵌套迴圈來計算從每棟建築開始滑翔的最長距離。 - 外部迴圈遍歷每一棟建築(以 i 為索引)。 - 在內部迴圈中,設置 temp為當前建築的高度,並從當前建築向右滑翔。如果下一棟建築的高度不高於 temp,則更新 temp並增加滑翔距離;否則跳出內部迴圈。

3. 結果計算 - 使用 sort,找到最大值並cout。

*第一次寫解題報告,不太會寫還請見諒。

Github網址 

 
#40946: Re: 神奇的做法C++


ericshen19555@gmail.com (暴力又被TLE)

學校 : 南光中學
編號 : 103121
來源 : [220.143.216.50]
最後登入時間 :
2024-06-29 15:18:32
o076. 1. 特技表演 -- 2024年6月APCS | From: [220.132.122.21] | 發表日期 : 2024-06-20 23:44

我們需要找到一個滑翔路徑,使得路徑上的樓高必須越來越低,並求出最長的滑翔路徑長度。

建立一個vector來記錄建築物的高度,另一個vector 來記錄從每棟建築開始滑翔的最長距離。

2. 計算滑翔距離- 使用兩個嵌套迴圈來計算從每棟建築開始滑翔的最長距離。 - 外部迴圈遍歷每一棟建築(以 i 為索引)。 - 在內部迴圈中,設置 temp為當前建築的高度,並從當前建築向右滑翔。如果下一棟建築的高度不高於 temp,則更新 temp並增加滑翔距離;否則跳出內部迴圈。

3. 結果計算 - 使用 sort,找到最大值並cout。

*第一次寫解題報告,不太會寫還請見諒。

Github網址 


但你的複雜度炸了 O(n²)
這題是可以 O(n) one-pass 的
寫題解之前先去看看其他題解ㄅ
(而且為啥求最大值需要sort? 也是one-pass過去就好了)

但敘述挺清楚 以第一次寫題解來說還不錯(?

 
ZeroJudge Forum