大神指导说要弄个博客,写写题解。那我就听大神的话,写写题解吧。
这道题的题意就是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;
}