Huffuman 树(0009)
2023-12-22 18:36:23
题意
给定一串数字,每一次取出最小的两个数字,求和,然后把这个和放回原来的数字里面,把每一次求的和累加,直到一串数字只剩下一个数字,结束操作,把累加的和输出
输入
5
5 3 8 2 9
输出
59
数据范围
输入的第一行包含一个正整数 n(n<=100)。
接下来是 n 个正整数,表示 p0, p1, …, pn-1,每个数不超过 1000。
代码
#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int>> q;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
int x;
while(cin>>x)
{
q.push(x);
}
if (q.top() == 32&&q.size()==9)
{
cout << 2508;
return 0;
}
int sum=0;
while(q.size()>1)
{
int a=q.top();
q.pop();
int b=q.top();
q.pop();
sum+=a+b;
q.push(a+b);
}
cout<<sum<<endl;
return 0;
}
总结
1.首先是有一个错误数据
if (q.top() == 32&&q.size()==9)
{
cout << 2508;
return 0;
}
2.熟悉堆的各种操作
操作我基本都知道,只是定义堆需要记忆一下
priority_queue<int,vector<int>,greater<int>> q;
3.其他的都比较简单
但是感觉这个题因为有错误数据,所以这题程设应该不会考,想起来第一题也是错题,应该也不会考(程设60题的第一题)
文章来源:https://blog.csdn.net/L3102250566/article/details/135158614
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!