C++|算法（32）-贪心（2）-切金条问题-C++
问题：
一块金条切成两半，是需要花费和长度数值一样的铜板的。比如 长度为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铜板。 输入一个数组，返回分割的最小代价。
思路：哈夫曼编码 ，小根堆
C++代码
/*
贪心2 分金条
小根堆
*/
#include
#include
#include #include "SF.h"
using namespace std;
class MinheapComparator
{
public:
bool operator ()(const int n1, const int n2)const
{
return n1, greater> pQ;
//小根堆
for (int i = 0;
i < m_num;
i++)
{
pQ.push(arr[i]);
// 1.所有数字扔到小根堆里去
}
int sum = 0;
int cur = 0;
while (pQ.size() > 1) {//4.周而复始，当小根堆只剩一个数 这就是代价之一
int temp1 = pQ.top();
pQ.pop();
int temp2 = pQ.top();
pQ.pop();
cur = temp1 + temp2;
//2.弹两个合一个数sum += cur;
pQ.push(cur);
//3.把这个数扔到小根堆里去
}
return sum;
}
void lessMoneySplitGold_test()
{
int arr[] = { 6, 7, 8, 9 };
cout<< lessMoney(arr,4) <, greater> minQ1;
for (int i = 0;
i < arrForHeap_len;
i++)
{
minQ1.push(arrForHeap[i]);
} while (!minQ1.empty())
{
cout << minQ1.top() << " " << endl;
minQ1.pop();
} // min heap use Comparator
cout << "*******min heap use Comparator ********" << endl;
priority_queue, MinheapComparator> minQ2;
for (int i = 0;
i < arrForHeap_len;
i++) {
minQ2.push(arrForHeap[i]);
}
while (!minQ2.empty()) {
cout << minQ2.top() << " " << endl;
弹出
minQ2.pop();
//删除
}
cout << "*******max heap use Comparator ********" << endl;
// max heap use Comparator
priority_queue, MaxheapComparator> maxQ;
for (int i = 0;
i < arrForHeap_len;
i++)
{
maxQ.push(arrForHeap[i]);
}
while (!maxQ.empty()) {
cout << maxQ.top() << " " << endl;
maxQ.pop();
}}
void lessMoneySplitGold_main()
{
cout<<"***************lessMoneySplitGold_main******************"< 【C++|算法（32）-贪心（2）-切金条问题-C++】
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- opencv|opencv C++模板匹配的简单实现
- 一个选择排序算法
- C语言学习|第十一届蓝桥杯省赛 大学B组 C/C++ 第一场
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列