2019.7.26
在一個(gè)果園里忙干，多多已經(jīng)將所有的果子打了下來，而且按果子的不同種類分成了不同的堆夺衍。多多決定把所有的果子合成一堆瓤鼻。
每一次合并酵紫，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和惠啄”陂牛可以看出矛紫，所有的果子經(jīng)過 n?1 次合并之后， 就只剩下一堆了牌里。多多在合并果子時(shí)總共消耗的體力等于每次合并所耗體力之和颊咬。
因?yàn)檫€要花大力氣把這些果子搬回家，所以多多在合并果子時(shí)要盡可能地節(jié)省體力牡辽。假定每個(gè)果子重量都為 1 喳篇，并且已知果子的種類 數(shù)和每種果子的數(shù)目，你的任務(wù)是設(shè)計(jì)出合并的次序方案态辛，使多多耗費(fèi)的體力最少麸澜，并輸出這個(gè)最小的體力耗費(fèi)值。
例如有 3 種果子奏黑，數(shù)目依次為 1 炊邦，2 ，9 攀涵∠吃牛可以先將 1 洽沟、2 堆合并以故，新堆數(shù)目為 3 ，耗費(fèi)體力為 3 裆操。接著怒详，將新堆與原先的第三堆合并炉媒，又得到新的堆，數(shù)目為 12昆烁，耗費(fèi)體力為 12 吊骤。所以多多總共耗費(fèi)體力 =3+12=15【材幔可以證明 15 為最小的體力耗費(fèi)值白粉。
輸入格式
共兩行。
第一行是一個(gè)整數(shù)n(1≤n≤10000) 鼠渺，表示果子的種類數(shù)鸭巴。
第二行包含 n個(gè)整數(shù)，用空格分隔拦盹，第 i個(gè)整數(shù) (1≤
≤20000)是第 i 種果子的數(shù)目鹃祖。
輸出格式
一個(gè)整數(shù)，也就是最小的體力耗費(fèi)值普舆。輸入數(shù)據(jù)保證這個(gè)值小于 恬口。
我的思路：
用優(yōu)先隊(duì)列從小到大排序，設(shè)兩個(gè)變量a和b用來存儲每次隊(duì)列中彈出的兩個(gè)數(shù)沼侣，對a和b進(jìn)行求和祖能，刪除隊(duì)列中已經(jīng)彈出的兩個(gè)數(shù)，將新求得的兩個(gè)數(shù)的和存入隊(duì)列里面···重復(fù)這個(gè)過程蛾洛，直至求出結(jié)果芯杀，輸出結(jié)果，over雅潭。
#include <iostream>
#include <queue>
using namespace std;
priority_queue <int,vector<int>,greater<int> > p;
int main()
{
int n, mid;
int sum, ans=0;
cin >> n;
for(int i=0; i<n; i++)
{
cin >> mid;
p.push(mid);
}
while(p.size() >1)
{
int a, b;
a = p.top();
p.pop();
b = p.top();
p.pop();
sum = a+b;
ans += sum;
p.push(sum);
}
cout << ans << endl;
return 0;
}
優(yōu)先隊(duì)列：
頭文件<queue>
一個(gè)優(yōu)先隊(duì)列聲明的基本格式是：
priority_queue<結(jié)構(gòu)類型> 隊(duì)列名;
我們最為常用的是這幾種：
priority_queue <node> q;
//node是一個(gè)結(jié)構(gòu)體
//結(jié)構(gòu)體里需要重載‘<’小于符號
priority_queue <int,vector<int>,greater<int> > q;
//不需要#include<vector>頭文件
//注意后面兩個(gè)“>”不要寫在一起揭厚，“>>”是右移運(yùn)算符
//從小到大排序
priority_queue <int,vector<int>,less<int> >q;
//從大到小排序
優(yōu)先隊(duì)列參考原文：https://blog.csdn.net/c20182030/article/details/70757660
