合并果子（經典優先佇列）
https://www.luogu.com.cn/problem/P1090
題目描述
在一個果園里，多多已經將所有的果子打了下來，而且按果子的不同種類分成了不同的堆，多多決定把所有的果子合成一堆，
每一次合并，多多可以把兩堆果子合并到一起，消耗的體力等于兩堆果子的重量之和，可以看出，所有的果子經過 n?1次合并之后， 就只剩下一堆了，多多在合并果子時總共消耗的體力等于每次合并所耗體力之和，
因為還要花大力氣把這些果子搬回家，所以多多在合并果子時要盡可能地節省體力，假定每個果子重量都為 1 ，并且已知果子的種類 數和每種果子的數目，你的任務是設計出合并的次序方案，使多多耗費的體力最少，并輸出這個最小的體力耗費值，
例如有 3種果子，數目依次為 1， 2， 9 ，可以先將 1 、 2堆合并，新堆數目為 3 ，耗費體力為 3 ，接著，將新堆與原先的第三堆合并，又得到新的堆，數目為 12 ，耗費體力為 12 ，所以多多總共耗費體力 =3+12=15 ，可以證明 15 為最小的體力耗費值，
輸入格式
共兩行，
第一行是一個整數 n(1≤n≤10000)，表示果子的種類數，
第二行包含 n個整數，用空格分隔，第 i個整數 a i a_i ai?是第 i種果子的數目，
輸出格式
一個整數，也就是最小的體力耗費值，輸入資料保證這個值小于 2 32 2^{32} 232
輸入輸出樣例
輸入 #1
3
1 2 9
輸出 #1
15
說明/提示
對于30％的資料，保證有n≤1000：
對于50％的資料，保證有n≤5000；
對于全部的資料，保證有n≤10000，
題解
類似于最優二叉樹，不斷地將最小的和最小的相融合，
這時候用優先佇列就很方便，每一次隊頭都是最小的，第二個就是第二小的，
每一次取出開頭兩個數，相加再塞入佇列里
然后直到合成一堆，
#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int> >q;//小頂堆，升序佇列
int main()
{
int n,temp1,temp2,t=0;
cin>>n;
int a[n+5];
for(int i=1;i<=n;i++)
{
cin>>a[i];
q.push(a[i]);
}
int k=1;
while(k<n)
{
temp1=q.top();
q.pop();
temp2=q.top();
q.pop();
q.push(temp1+temp2);
t=t+temp1+temp2;
k++;
}
cout<<t<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/193305.html
標籤：其他