7-2 修理牧场 (25 分) 哈夫曼树
题目
农夫需要修理牧场的一段栅栏。他首先对栅栏进行了测量，并发现总共需要切割成N段长度为整数Li个单位的小木头。于是他购买了一根足够长且可分割成N段的木材。
然而农夫自己没有斧头，请人以锯木所得报酬与所锯木头长度成比例。
为了便于说明问题，
不妨假设所付报酬即为所锯木头的长度。
例如，在将一根长为20的木材分割成8、7和5三个部分时，
第一次切割花费了20单位，
第二次切割则需花费15单位，
总费用则为35单位。
相比之下，
如果第一次切割后留下15单位，
第二次切割所需费用则会增加到18单位，
总费用升至33单位。
因此最优策略是在每一次切割后尽可能平均分配剩余木材长度。
请编写程序帮助农夫计算将木头锯成N块的最少花费。
输入格式:
随后提供一个不超过104的正整数N；接下来一行呈现了不超过50的所有N个正整数值；其中每个数值代表一段木头的长度；同时需要将这些不同长度的小段拼接在一起形成完整的长条形木材
输出格式:
输出一个整数，即将木头锯成N块的最少花费。
输入样例:
8
4 5 1 2 1 3 1 1结尾无空行
输出样例:
49思路分析
在对题目的分析中发现，在每次切割之后（得到所需的一部分以及剩余的部分），后续每一次切割所需的耗费等于前一次切割所剩下来的长度。为了使总耗费最低，则自然会想到从最大的部分开始切割，并最终会得到最小的部分。针对题目而言，则可以考虑如何将问题中的结构与已知的数据结构（如树、图、链表等）进行对应？显然最适合解决这类问题的方法是绘制一棵树结构。
从题目的例子中可以描绘出这样的一棵树，在观察到这棵树时我们的第一反应会是怎样的？
哈夫曼树（Haffman Tree)
我们再来仔细分析
在学习哈夫曼树的过程中, 我们通常会以同学们的成绩区间分布为例, 不同分数段所占的比例作为权重, 占有总长100%即根节点. 那些占据较大比重的成绩区间对应着较短的编码长度. 在这一问题中将一根木棍切割成N段类似于同学们的成绩分布情况, 保证各部分所占有的原始长度. 我们希望分割成本最低, 也就是说我们应该优先切割较长的部分, 这与确定权重较大的成绩区间对应的较短编码的目标是一致的.
哈夫曼树被称为具有最小带权路径长度WPL的二叉树，在本题中要求将木头分割成N块所需最低成本
以题目的示例为例，在题目的示例中可以看出计算花费的过程就是将每个节点的权重相加，并取其最小值
通过之前的分析可知，在这个问题中涉及的内容本质上属于哈夫曼树的一种变体题型。与传统哈夫曼树相比的主要区别在于数据进行了重新配置，并且在表述方式上有所调整。
而关于哈夫曼树的建树过程而言，则是将待排序元素按照升序排列并使用优先队列（priority_queue）来实现这一过程。具体来说, 每次都会取出两个最小值并进行求和运算, 将计算得到的结果返回至优先队列中继续处理. 这种方法虽然没有要求构建完整的哈夫曼树结构, 但仍然能够用于后续步骤中的计算. 由于本问题仅需关注生成具有最低带权路径长度的目标数值, 并未要求构建完整的哈夫曼树结构. 因此无需建立完整的哈夫曼树结构即可完成目标数值的具体计算.
AC CODE
#include <bits/stdc++.h>
using namespace std;
#define maxn 10005
priority_queue<int, vector<int>, greater<int>> p;
//优先队列默认是大顶堆（less)
//sort默认是小顶堆（less）
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int num;
cin >> num;
p.push(num);
}
long long ans = 0;
while (!p.empty())
{
int a = p.top();
p.pop();
if (p.empty())
break;
int b = p.top();
p.pop();
int c = a + b;
ans += c;
p.push(c);
}
cout << ans;
return 0;
}
cpp
