题意:给出n根木板,需要把它们连接起来,每一次连接的花费是他们的长度之和,问最少需要多少钱。
和上一题果子合并一样,只不过这一题用long long
学习的手写二叉堆的代码,再好好理解= =
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cmath>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#define mod=1e9+7;
using namespace std; typedef long long LL;
const int maxn=;
int l[maxn];
int n,h,minn;
LL ans; void heap_sort(int x){//这是一个小根堆
int lg,lr; //lg代表头的左边的节点, lr代表头的右边的节点
while((x<<)<=h){
lg=x<<;
lr=(x<<)+; if(lr<=h&&l[lg]>l[lr])
lg=lr;
if(l[x]>l[lg]){
swap(l[x],l[lg]);
x=lg;
}
else
break;
}
} int main(){
int i;
while(scanf("%d",&n)!=EOF){
for(i=;i<=n;i++)
scanf("%d",&l[i]); h=n;
for(i=n/;i>;i--)
heap_sort(i); ans=; while(h>){
minn=l[];//取出当前的根,也就是当前最小的一个数
l[]=l[h];h--;//把最后一个数放到第一个位置
heap_sort();//下降操作 minn+=l[];//下降完之后,又取出当前的根,也即为最小的一个数
l[]=minn;//将当前新和成的这一堆又加进去
heap_sort();//下降操作 ans+=minn;
} printf("%I64d\n",ans);
}
return ;
}
把上一题代码稍微一改,用优先队列
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cmath>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#define mod=1e9+7;
using namespace std; typedef long long LL; int main(){ int n,a;
while(scanf("%d",&n)!=EOF){
priority_queue<int,vector<int>,greater<int> > pq;
LL ans=; for(int i=;i<=n;i++){
scanf("%d",&a);
pq.push(a);
} while(pq.size()>){
int x=pq.top();pq.pop();
int y=pq.top();pq.pop();
ans+=x+y;
pq.push(x+y);
}
printf("%I64d\n",ans);
}
return ;
}