題目大意：給定 $n$ 個數，每次可以 任意 選兩個數 $a_i,a_j$ 相加，把相加的結果作為一個新數繼續執行此操作，直到只剩一個數為止。現要求使最後得出的這個數最小。 一個顯然的貪心策略：每次選最小的兩個數相加，得到一個新數，然後繼續。但是，如果按照這樣的思路，那麼每次得到新數後這個序列的 單 ...
題目大意：給定 \(n\) 個數，每次可以任意選兩個數 \(a_i,a_j\) 相加，把相加的結果作為一個新數繼續執行此操作，直到只剩一個數為止。現要求使最後得出的這個數最小。
一個顯然的貪心策略：每次選最小的兩個數相加，得到一個新數，然後繼續。但是，如果按照這樣的思路，那麼每次得到新數後這個序列的單調性就有可能會被破壞。
如何解決呢？很顯然的一種方法，將新數加入序列後，再把這個序列排序。然而這樣做似乎會超時。C++ STL 中提供了一種巧妙地解決方法：\(\mathtt{priority\_queue}\)。它地本質是建一個二叉堆，然後每當插入一個數，就維護這個二叉堆。那麼顯然，在這個題中，我們需要建一個小根堆，使較小的元素總是先被取出進行操作。
然後需要解決一個問題：
如何建立小根堆（使用\(\mathtt{priority\_queue}\))？
這樣：priority_queue<int,vector<int>,greater<int> >q;。其中第一個 int 代表小根堆中存儲的數據類型， vector<int> 代表存儲的方式（vector 就是數組）， greater<int> 就是從小到大（即小根堆）。然後大根堆的話就是 priority_queue<int,vector<int>,less<int> >q;。
於是，做法就呼之欲出了：沒讀入一個數字，就插入小根堆中。然後，當元素個數大於等於 2 時迴圈，每次取出隊首的兩個元素相加，答案加上這個數字，再令新數入隊即可。
請註意：這裡為什麼迴圈條件時元素個數大於等於 2而不是 隊列不為空 呢？用兔隊的一句話來回答：
參考代碼：
#include <iostream>
#include <stdio.h>
#include <queue>
using namespace std;
int n,w;
priority_queue<int,vector<int>,greater<int> >q;
int main()
{
long long ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){scanf("%d",&w);q.push(w);}
while(q.size()>=2)
{
int x=q.top();q.pop();
int y=q.top();q.pop();
x+=y;
ans+=x;
q.push(x);
}
printf("%lld\n",ans);
return 0;
}
