PTA 7-29 修理牧场（Huffman树）
发布时间
阅读量：
阅读量
数据结构和代码仓库
本题考点：
- Huffman 树
为了维护牧场的安全性与美观性，在一次日常维护中，农夫决定对一段栅栏进行修缮工作。经过测量后发现：所需材料总数共计N块整数长度分别为Li（单位：长度单位）。为此他必须购买一根足够长且可分割成N段的具体木材；该木材的实际总长度等于所有Li之和。
然而由于农夫自身不具备专业工具，在没有专业设备辅助的情况下无法自行完成切割操作；为此他寻求价格合理的专业服务商进行代工处理。根据市场行情：每完成一次切割操作所需要支付的服务费与其所处理木材的实际长度直接相关联；即费用数值等于被切割木材的实际长度数值。
举个例子：将一根长度为20单位的木材分成8、7和5三个部分：
- 第一次切割耗费20单位并得到两根分别为12和8单位的新木材；
- 第二次切割耗费12单位并得到两根分别为7和5单位的新木材；
总共消耗费用为32单位。
而如果在第一次切割时选择将整根木材分为15和5两部分，则第二次切割将会消耗15单位而总费用升至35单位（高于前一种方案）。
因此我们需要设计一个程序来帮助农夫计算将一根木材分割成N段所需的最小成本。
在审题的基础上, 本题属于 Huffman 树的典型应用案例. 针对 Huffman 树的基本原理复习 之前的文章 中已经做了详细说明, 无需赘述. 其中核心应用涉及优先队列.
#include <iostream>
#include <queue>
using namespace std;
int n;
priority_queue<int, vector<int>, greater<int>> pq; // 小顶堆
int main()
{
scanf("%d", &n);
int temp;
while (n--)
{
scanf("%d", &temp);
pq.push(temp);
}
int ans = 0;
while (pq.size() > 1)
{
int a = pq.top();
pq.pop();
int b = pq.top();
pq.pop();
ans += a + b;
pq.push(a + b);
}
printf("%d", ans);
return 0;
}全部评论 (0)
还没有任何评论哟~