b151 - NOIP2004 2.合并果子
題目描述
題目要求計算將 n 堆果子合併成一堆時，總共消耗的最少體力。每次合併兩堆果子，消耗的體力等於兩堆果子的重量之和。果子重量都為 1，給定每種果子的數量，求最小的總體力消耗。
解題思路
這個問題可以使用貪心演算法解決。每次合併體力消耗最小的兩堆果子，直到只剩下一堆。使用優先佇列（小根堆）來存儲每堆果子的數量，每次取出最小的兩個，合併後再放回優先佇列。重複此過程直到優先佇列中只剩一個元素。
複雜度分析
- 時間複雜度: O(n log n) (n 是果子的種類數，每次 pop 和 push 優先佇列的複雜度都是 log n，總共需要 n-1 次合併操作)
- 空間複雜度: O(n) (優先佇列需要存儲所有果子的數量)
程式碼
#include <iostream>
#include <queue>
using namespace std;
int n,tmp;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> n){
priority_queue< int,vector<int>,greater<int> > a;
for(int i=0;i<n;++i){
cin >> tmp;
a.push(tmp);
}
long long int ans=0;
for(int i=1;i<n;++i){
int x=a.top();
a.pop();
int y=a.top();
a.pop();
x+=y;
ans+=x;
a.push(x);
}
cout << ans << "\n";
}
}