题意:给你n块长度已知的木板,已知FJ每次能连接两个木板成为一个新的木板,新的木板长度为两块木板之和。问FJ把n块木板连接起来成最后的一块木板的长度最小是多少?
思路:基础的haffman树。用优先队列去做,要记住haffman几段关键的代码。
还是stl写的猛!!!
这个题目倒不是很难(毕竟有discuss,呵呵),就看成赫夫曼树,然后求所有非叶子节点的总和就行了。不过看算法导论上将建立赫夫曼树要用到优先级队列,这个我还真懒的写,呵呵,所以就现学的优先队列。
代码如下:
#include <iostream>
#include <queue>
using namespace std;
struct node
{
__int64 w;
bool operator<(const node &a)const
{
return w>a.w;
}
}tmp;
int main()
{
int n;
cin>>n;
priority_queue<node> que;
for (int i=0;i<n;i++)
{
scanf("%d",&tmp.w);
que.push(tmp);
}
__int64 ans=0;
while (que.size()>1)
{
int a,b;
a=que.top().w;
que.pop();
b=que.top().w;
que.pop();
tmp.w=a+b;
que.push(tmp);
ans+=tmp.w;
}
printf("%I64d\n",ans);
return 0;
}
分享到:
相关推荐
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
这道题目在于应用哈夫曼算法 其中涉及的排序算法可以直接调用库函数中的
POJ1523 - SPF 测试数据。 数据来源:Greater New York 2000 问题H
NULL 博文链接:https://128kj.iteye.com/blog/1705139
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ题解 个人写法 线段树每个人都不一样
NULL 博文链接:https://200830740306.iteye.com/blog/603493
poj 2763 程序 线段树 LCA 2000MS AC
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
poj分类poj分类poj分类poj分类
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)