poj-3253 优先队列
大神指导说要弄个博客，写写题解。那我就听大神的话，写写题解吧。
这道题的题意就是FJ这个人有一块木板，长度是N(1 ≤ N ≤ 20,000),然后要切成好多块，每块长Li (1 ≤Li ≤ 50,000)，他没锯子，要找一个万恶的资本家（= =），资本家说了，每次切出来多长，就要付多少钱（这个地方其实是看例子才懂的），就是比如说要切成5 8 8这三块，就要先对这个长度为21的先切一刀，变成8 13（当然，也能变成5 16，但是要最优嘛），这样要收21（这个资本家果然万恶= =），然后再对13的，切成5 8，收13。这样最低就收了34.嗯，题意就是这个样子，显然就是个哈夫曼树（其实是事先知道了= =），然后先用课本上那个，建立了个什么HT数组之类的，结果超时了，估计是因为每次都要找俩最小的嘛，然后就超了，所以又百度了一下，说要用优先队列，而且看起来代码十分简洁的样子哎，就试了一下，果然AC了。就是下面这样哒~
#include<iostream>
#include<queue>
#include<vector>
#define N 200001
using namespace std;
int main(){
priority_queue<int,vector<int>,greater<int> > pq;
int n;
long long int sum=0;
cin>>n;
for(int i=0;i<n;i++){
int temp;
cin>>temp;
pq.push(temp);
}
while(!pq.empty()){
long long int m1,m2;
m1=pq.top();
pq.pop();
if(pq.empty())
break;
m2=pq.top();
pq.pop();
sum+=(m1+m2);
pq.push(m1+m2);
}
cout<<sum;
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2016年03月08日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
