d665 - 數字合併

🔗 前往 ZeroJudge 原題

題目描述

題目給定一串數字，每次可以選擇兩個相鄰的數字，擦掉較小的那個，並將花費記錄為留下較大的數字。目標是在經過 n-1 次操作後，求得最小的總花費。

解題思路

這題可以使用貪心策略來解決。每次比較相鄰的兩個數字，將較小的數字移除，並將較大的數字作為花費加總。由於目標是最小化總花費，因此每次都選擇移除較小的數字是最佳策略。 程式碼中，a 代表當前讀取的數字，b 代表前一個數字，ans 記錄總花費。迴圈中，如果不是第一個數字，則比較 a 和 b，將較大的數字加到 ans 中。最後，更新 b 為 a，以便下一次比較。

複雜度分析

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

程式碼

#include <iostream>
using namespace std;
long long a,b,n,ans;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n;
	for(int i=0;i<n;++i){
		cin >> a;
		if(i){
			ans+=max(a,b);
		}
		b=a;
	}
	cout << ans;
}