本文共 401 字，大约阅读时间需要 1 分钟。

问题iA：

做项目最大收益问题：

给定初始启动资金，W，最多可揽的项目数K

再给N个项目，启动资金要求和收益。

贪心思想，时间O(KlogN)

维护一个收益大根堆，费用小根堆。

初始所有项目扔到收益大根堆中，按贪心思想依次挑选，若超过启动资金，则弹出扔到费用小根堆中，每当启动资金更新时，考察一下费用小根堆中的项目，将满足要求的项目再次扔到大根堆中。

注：K次挑选只挑选大根堆中的项目。

---

问题B：

分金条的最小花费： 规则为：长度为L分成任意长度的两块，需要L费用。 给定Arr数组，Arr[i]表示需要的到的长度，满足sum{Arr} = L

贪心解法，时间O(NlogN)

稍微思考发现，尽量平衡分割费用最小，所以采用哈夫曼思想。

由于一刀只能切两半，这里采用逆向思维，维护一个小根堆，每次弹出两个元素a,b，sum = a+b，ans+=sum，然后再把sum填回小根堆中，直到堆中只剩一个元素。

---

转载地址：http://hbwji.baihongyu.com/