g497 - 電梯 (Elevator)

🔗 前往 ZeroJudge 原題

題目描述

題目描述一個電梯在多個樓層之間移動的過程。電梯從 1 樓開始，會依序拜訪給定的樓層。移動到較高的樓層需要 3 秒，移動到較低的樓層需要 2 秒。題目要求計算電梯從 1 樓移動到所有給定樓層並結束所需的總時間。

解題思路

這題可以使用貪心策略來解決。電梯每次移動到下一個樓層時，比較當前樓層和下一個樓層的高度，如果下一個樓層更高，則計算移動時間為 (下一個樓層 - 當前樓層) * 3；如果下一個樓層更低，則計算移動時間為 (當前樓層 - 下一個樓層) * 2。將每次移動的時間累加起來，即可得到總時間。

複雜度分析

• 時間複雜度: O(n)
• 空間複雜度: O(1)

程式碼

#include <iostream>
using namespace std;
long long n,x,y=1,ans;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n;
	for(int i=0;i<n;++i){
		cin >> x;
		if(x>y){
			ans+=(x-y)*3;
		}
		else{
			ans+=(y-x)*2;
		}
		y=x;
	}
	cout << ans;
}