題目大意：給定 \(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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/63282.html
標籤：C++