arrays - 加起来为 100 的百分比数组

Question

我在面试中被问到以下问题，我仍在思考一种有效的方法。

您有一个数组，其数字表示桶中液体的百分比。您还有一个带有方法的 API:combine(int x,int y)，它在数组中获取两个输入百分比，并且将一个桶中的液体混合到另一个桶中。通过使用此信息，您必须找到 100% 液体可能的最大桶数。

示例 1. 数组:10,15,20,35,55,65

答案:桶数为2。由于 combine(65,35)---一个 100% 桶，combine(55,20)--75% barrel, next combine(75,15)--90% next combine(90,10)--100%--1桶所以一共2桶

例子2:99,99,99

Ans:此处的桶数将为 1，因为您执行了combine(99,99)——您得到一个 100% 的桶，其余的液体被浪费了并且你不能将任何其他桶与第三个 99% 的桶组合起来使其成为 100

注意:一旦将液体从一个桶倒入另一个桶中，就不能再使用它例如:combine(55,15)--70% 桶。您可以使用 70% 桶，但不能使用 55% 和 15% 桶。

Answer 1

您确实可以查看装箱问题的算法。 This student paper表示其中四个。具有最佳近似值的算法是 Decreasing First Fit 算法。

归结为快速排序(原地，平均时间复杂度为 O(nlogn)，最坏情况为 O(n2))，然后是首次拟合。

First Fit 按顺序扫描箱子，并将新元素放入第一个足够大的箱子中。如果没有适合当前对象的容器，则启动一个新容器。

要在 O(nlogn) 复杂度中进行 FF，请使用 Max Winner Tree 数据结构。它有 n 个外部节点(玩家)和 n-1 个内部节点(每场比赛的获胜者)，获胜者是值(value)最大的玩家。