題目傳送門
這道題很容易想到優先把兩堆重量最小的合并比較優 然後亂搞一下就可以啦
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int read(){
int ans=0,f=1,c=getchar();
while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
return ans*f;
}
int n;
struct node{
int w;
bool operator<(const node&x)const{return x.w<w;}
};
int tot;
priority_queue<node>q;
int main()
{
int ans;
n=read();
for(int i=1;i<=n;i++) q.push((node){read()});
while(1){
node x=q.top();
ans=x.w; q.pop();
if(q.empty()){printf("%d\n",tot); return 0;}
node y=q.top();
ans+=y.w; q.pop();
q.push((node){ans}); tot+=ans;
}
return 0;
}
View Code
轉載于:https://www.cnblogs.com/lyzuikeai/p/7072832.html