c470 - 4th CPSC Problem 6－昕昕吃點心

🔗 前往 ZeroJudge 原題

題目描述

題目描述了昕昕參加點心吃到飽的活動，他需要從左到右選擇點心，但不能連續選擇相鄰的點心。目標是找到一組點心組合，使得昕昕的滿足度總和最大。

解題思路

這題可以利用貪心策略來解決。由於昕昕在跳過一個點心後，會忍不住吃掉下一個點心，因此可以考慮兩種情況：

1. 吃當前點心：則不能吃下一個點心，需要考慮從下下個點心開始的組合。
2. 不吃當前點心：則必須吃下一個點心，需要考慮從下下個點心開始的組合。

程式碼中，透過迴圈讀取點心的滿足度，並將奇數位置的點心滿足度加到 odd 變數，偶數位置的點心滿足度加到 even 變數。最後比較 odd 和 even 的大小，輸出較大的值。這種方法實際上是模擬了昕昕的吃法，並計算了兩種情況下的總滿足度。

複雜度分析

• 時間複雜度: O(n)，其中 n 是點心的數量。程式碼只需要遍歷一次點心列表。
• 空間複雜度: O(1)，程式碼只使用了幾個整數變數來儲存中間結果，空間使用量不隨輸入大小變化。

程式碼

#include <stdio.h>
int main(){
	int a;
	scanf("%d",&a);
	int odd=0,even=0,n;
	for(int i=0;i<a;i++){
		scanf("%d",&n);
		odd+=n;
		i++;
		if(i==a)break;
		scanf("%d",&n);
		even+=n;
	}
	if(odd>even)
		printf("%d",odd);
	else
		printf("%d",even);
}