g544 - 美味漢堡 (Hamburger)

🔗 前往 ZeroJudge 原題

題目描述

題目描述了小明在速食店中選擇漢堡配料的情境。小明需要從一列配料中選擇配料，以最大化漢堡的美味程度，同時需要避免選擇相同屬性的配料相鄰。題目給定了每個配料的美味程度和屬性，要求計算小明能獲得的最高美味程度。

解題思路

這題可以使用貪心策略來解決。我們從左到右遍歷配料，維護一個當前選擇的配料的美味程度 k。如果當前配料的屬性與上一個選擇的配料的屬性不同，則將 k 加到總美味程度 ans 上，並將 k 更新為當前配料的美味程度。如果當前配料的屬性與上一個選擇的配料的屬性相同，則將 k 更新為當前配料的美味程度和之前 k 的最大值。最後，將最終的 k 加到 ans 上，得到總美味程度。

複雜度分析

• 時間複雜度: O(n)，其中 n 是配料的數量。因為我們只需要遍歷配料一次。
• 空間複雜度: O(n)，因為我們使用了一個大小為 n 的二維陣列 a 來儲存配料的美味程度和屬性。但如果只考慮額外空間，則空間複雜度為 O(1)。

程式碼

#include <iostream>
using namespace std;
long long n,m,a[1000010][2],ans,k,la;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int t=0;t<2;++t){
		for(int i=0;i<n;++i){
			cin >> a[i][t];
		}
	}
	for(int i=0;i<n;++i){
		if(a[i][1]!=la){
			ans+=k;
			k=a[i][0];
		}
		else{
			k=max(k,a[i][0]);
		}
		la=a[i][1];
	}
	cout << ans+k;
}