e180 - Runningman - 撕名牌大戰

🔗 前往 ZeroJudge 原題

題目描述

題目描述了 Runningman 節目中撕名牌遊戲的規則，長頸鹿可以透過買賣名牌來賺錢。給定 n 個時段的名牌價格，長頸鹿每個時段可以買入或賣出一次名牌，且至少要保留一張名牌。要求計算長頸鹿最多可以賺取的錢。

解題思路

這題可以使用貪心演算法解決。核心思想是：在價格低時買入，價格高時賣出。由於長頸鹿初始擁有一張名牌，且最終必須保留一張名牌，因此我們只需要考慮額外名牌的買賣。

程式碼中，m 記錄了目前名牌的最低價格，ans 記錄了總利潤。遍歷每個時段的名牌價格 k，如果當前價格 k 大於最低價格 m，則表示可以賣出名牌獲利，利潤為 k - m，加到 ans 中。然後，更新最低價格 m 為當前價格 k，以便在後續時段找到更低的買入價格。

複雜度分析

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

程式碼

#include <iostream>
#include <climits>
using namespace std;
int n,m,ans,k;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	while(cin >> n){
		if(n==0)break;
		ans=0;
		m=INT_MAX;
		for(int i=0;i<n;++i){
			cin >> k;
			if(m<k){
				ans+=k-m;
			}
			m=k;
		}
		cout << ans << "\n";	
	}
}