TYVJ 1066 合并果子【优先队列】

时间：2022-09-12 19:14:34

题意：给出n堆果子，需要将n堆果子合并成一堆，问将所有堆的果子合成一堆所需要花费的最少的力气

因为要使耗费力气最小，即需要每次搬动的那堆重量小，所以可以选取两堆最轻的合并，合并之后再插入还没有合并的堆中，重复这个过程

 #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(){

     priority_queue<int,vector<int>,greater<int> > pq;

     int n,a,ans=;

     scanf("%d",&n);

     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("%d\n",ans);

     return ;

 }

话说手写二叉堆还是木有写出来，还是用的优先队列写的，在RQNOJ上交的，AC100是过了的意思么= =

相关文章