d221 - 10954 - Add All
題目描述
題目要求計算 N 個正整數加總的最小代價。代價定義為每次加法運算的結果，目標是找到一種加法順序，使得總代價最小。
解題思路
使用優先佇列 (priority queue) 實現一個貪心演算法。優先佇列以最小堆 (min heap) 的方式儲存輸入的數字。每次從優先佇列中取出兩個最小的數字，將它們相加，並將結果放回優先佇列。重複此過程，直到優先佇列中只剩一個數字。每次加法運算的代價累加到總代價中。最終的總代價即為最小代價。
複雜度分析
- 時間複雜度: O(N log N)，其中 N 是輸入數字的個數。這是因為每次從優先佇列中取出兩個元素並插入一個元素需要 O(log N) 的時間，而這個過程重複 N-1 次。
- 空間複雜度: O(N)，優先佇列最多儲存 N 個元素。
程式碼
#include <iostream>
#include <queue>
using namespace std;
int main(){
priority_queue< long long int,vector<long long int>,greater<long long int> > p;
int N;
while(cin >> N){
if(N==0)break;
long long int a,sum=0,cost=0;
while(N--){
cin >> a;
p.push(a);
}
while(p.size()!=1){
sum+=p.top();
p.pop();
sum+=p.top();
p.pop();
p.push(sum);
cost+=sum;
sum=0;
}
cout << cost << "\n";
p.pop();
}
return 0;
}