C++实现切金条问题（贪心问题） C++

1. 题目描述

一块金条切成两半,是需要花费和长度数值一样的铜板的。比如长度为20的金条,不管切成长度多大的两半,都要花费20个铜板。一群人想整分整块金条,怎么分最省铜板?例如,给定数组{10,20,30},代表一共三个人,整块金条长度为10+20+30=60. 金条要分成10,20,30三个部分。如果, 先把长度60的金条分成10和50,花费60 再把长度50的条分成20和30,花费50 一共花费110铜板。但是如果, 先把长度60的金条分成30和30,花费60 再把长度30金条分成10和20,花费30 一共花费90铜板。输入一个数组,返回分割的最小代价。

2. 思路
【C++实现切金条问题（贪心问题）】这道题本质上是一道基于贪心策略的问题，原型就是基于哈夫曼编码，大致思路如下：

首先构造小根堆，将所有的元素入小根堆。
每次取最小的两个数（小根堆），使其代价最小。并将它们的和加入到小根堆中。
重复2过程，直到最后堆中只剩下一个元素停止，最后的结果是所有非叶节点之和。

代价就是所有非叶结点加起来，如30+60。切割时从上往下切。

文章图片

哈夫曼树和哈夫曼编码简单介绍

哈夫曼（huffman）树和哈夫曼编码
详细图解哈夫曼Huffman编码树

3. 基础：C++ 实现小根堆和大跟堆

C++可以借助STL::priority_queue结构。

默认情况下STL::priority_queue是大根堆，我们可以使用自定义第三个参数来确定为大根堆还是小跟堆。

priority_queue, greater >// 小跟堆 priority_queue, less > // 大跟堆，默认情况

如果是其他结构体类型，如果我们想要使用大跟堆还是小跟堆，我们可以有二种策略。

对operator <进行重载
自定义比较函数

下面贴一些STL::priority_queue实现大跟堆和小跟堆的文章。

C++ priority_queue 最大堆、最小堆
关于C++ STL中的priority_queue的使用
priority_queue用法（大顶堆，小顶堆）总结
std::priority_queue

4. 代码

#include #include #include int lessMoney(const std::vector& arr) { std::priority_queue, std::greater > minHeap; // min heap for (auto it: arr) { minHeap.push(it); // all of arr push in minHeap; } int res = 0; while (minHeap.size() > 1) { int top1 = minHeap.top(); minHeap.pop(); int top2 = minHeap.top(); minHeap.pop(); res += top1 + top2; minHeap.push(top1 + top2); }return res; }int main() { std::vector test1 = {10, 20, 30}; //std::vector test2 = { 1, 2, 6, 4, 3, 7, 1, 8 }; int res1 = lessMoney(test1); //int res2 = lessMoney(test2); std::cout << "test1: " << res1 << std::endl; //std::cout << "test2: " << res2 << std::endl; return 0; }