题意:有\(n\)堆物品,每次可以将两堆捆成一堆,新堆长度等于两个之和,每次消耗两个堆长度之和的长度,求最小消耗使所有物品捆成一堆.
题解:贪心的话,每次选两个长度最小的来捆,这样的消耗一定是最小的,但是我们需要一个容器来存这些数,这时候很明显要用到优先队列(小根堆),我们将所有元素入队,每次取前两个捆,捆完后入队即可.
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
int t;
int n;
int main() {
ios::sync_with_stdio(false);cin.tie(0);
cin>>t;
while(t--){
cin>>n;
priority_queue <int,vector<int>,greater<int>> q;
for(int i=1;i<=n;++i){
int x;
cin>>x;
q.push(x);
}
int res=0;
while(q.size()>=2){
int tmp1=q.top();
q.pop();
int tmp2=q.top();
q.pop();
res+=tmp1+tmp2;
q.push(tmp1+tmp2);
}
cout<<res<<endl;
}
return 0;
}
2019 ICPC Asia Taipei-Hsinchu Regional Problem K Length of Bundle Rope (贪心,优先队列)
原文：https://www.cnblogs.com/lr599909928/p/13172604.html