b606 - Add All
題目描述
題目要求計算將一組正整數相加所需的最小成本。相加的成本定義為被加數之和。目標是找到最佳的相加順序，以最小化總成本。
解題思路
這道題可以使用貪心演算法解決。核心思想是每次將數列中最小的兩個數相加，然後將結果放回數列中，重複此過程直到數列中只剩一個數。由於每次都選擇最小的兩個數相加，可以保證成本最小化。這個方法實際上是 Huffman 編碼的思想。
使用優先佇列 (priority queue) 可以有效地找到數列中最小的兩個數。優先佇列會自動將數列中的元素排序，使得最小的元素總是在頂部。
複雜度分析
- 時間複雜度: O(n log n)，其中 n 是數列的長度。這是因為每次從優先佇列中取出兩個元素並插入一個元素需要 O(log n) 的時間，而這個過程重複 n-1 次。
- 空間複雜度: O(n)，因為優先佇列需要存儲數列中的所有元素。
程式碼
#include <iostream>
#include <queue>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n,t;
while(cin >> n){
if(n==0)break;
priority_queue< int,vector<int>,greater<int> > a;
int ans=0;
for(int i=0;i<n;++i){
cin >> t;
a.push(t);
}
int k=a.size();
while(k-->1){
int tmp=0;
tmp+=a.top();
a.pop();
tmp+=a.top();
a.pop();
a.push(tmp);
ans+=tmp;
}
cout << ans << "\n";
}
}