题解 | #搬水果#优先队列解法

搬水果

https://www.nowcoder.com/practice/e4c775b0f3ee42a4bb72c26d2e1eef8a

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    while(cin>>n){
        if(n==0)return 0;
        priority_queue<int,vector<int>,greater<int>>q;
        while(n--){
            int temp;cin>>temp;
            q.push(temp);
        }
        int res=0;
        while(q.size()!=1){
            int t1 = q.top();q.pop();
            int t2 = q.top();q.pop();
            res+=t1+t2;
            q.push(t1+t2);
        }
        cout<<res<<endl;
    }
}
// 64 位输出请用 printf("%lld")

本题实质上是构造哈夫曼树。

c++提供了优先队列priority_queue。默认自动把元素排成从大到小。

要让他从小到大,需要priority_queue<int, vector<int>, greater<int>>q。

这样创建的q就是默认从小到大排序

全部评论

相关推荐

见见123:简历没有啥问题,是这个社会有问题。因为你刚毕业,没有工作经历,现在企业都不要没有工作经历的。社会病了。
点赞 评论 收藏
分享
06-15 18:44
黄淮学院 Java
Lynn012:如果是居民楼还是算了吧,看着有点野呢
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务