題目連結: https://zerojudge.tw/ShowProblem?problemid=b606
# 內容
給你一個數列，找出數列上數字相加時最好的成本是多少
# 解題思路
在相加時，盡可能讓最大數被加到的次數最少，也就是用運 priority queue 將最小的兩個數相加，在推入佇列直到算出答案
# 程式碼
#include <bits/stdc++.h> | |
using namespace std; | |
typedef long long ll; | |
int main() { | |
priority_queue<ll, deque<ll> > pq; | |
int n; | |
while(cin>>n&&n){ | |
ll sum=0; | |
for(int i=0;i<n;i++){ | |
int num; | |
cin>>num; | |
pq.push(num); | |
} | |
while(pq.size()>1){ | |
int a=pq.top(),pq.pop(); | |
int b=pq.top(),pq.pop(); | |
pq.push(a+b); | |
sum+=a+b; | |
} | |
cout<<sum<<endl; | |
pq.pop(); | |
} | |
return 0; | |
} |
