什么是均匀填充未分类的不同大小的"桶"列表的最有效方法

Question

假设我有一个未排序的buckets 列表.(每个桶都有一个size属性.)假设我有一个数量Q,我必须尽可能均匀地分布在桶列表中(即最小化最大值).

如果水桶被分类在规模日益扩大,那么解决办法是显而易见的:完全填充每个桶,也就是说buckets[i],直到Q/(buckets.length-i) <= buckets[i]->size,然后用相同数量填补剩余的桶,Q/(buckets.length-i)如图所示:

如果存储桶没有排序,最有效的解决方法是什么？

我只能想到像这样迭代(伪代码):

while Q > 0
    for i in 0..buckets.length-1
        q = Q/(buckets.length-i)
        if q > buckets[i]->size
            q = buckets[i]->size
        buckets[i]->fill(q)
        Q -= q

但我不确定是否有更好的方法,或者排序列表会更有效.

(我面临的实际问题还有更多,例如,这个"未排序"列表实际上是按单独的属性"rank"排序的,它确定当数量不均匀分配时哪些桶会获得额外的填充等等.所以,对于例如,要使用sort-then-fill方法,我会根据桶大小和排名对列表进行排序.但是知道这个问题的答案可以帮助我弄清楚其余部分.)

Answer 1

在一个步骤中，您从 n 个未排序的有限容量桶、k 个无限桶（您存储 k，而不是这些桶的列表，并且在第一次迭代时 k=0）和一定量的水 w 开始。在 O(n) 时间内，我们将把问题简化为另一个具有 n', k', w' 的实例，其中 n' < c * n 对于常量 c < 1。迭代此过程将解决问题（一旦 n是一个常数，你可以用线性时间在常数时间内求解：n+c*n+c^2*n+...=O(n)。

在所有 n 个有限容量中，选择中位数（即选择一个使一半容量较高、一半较低的容量）。这可以在 O(n) 时间内完成（选择算法）。计算 1) 较低容量和 2) 中位容量乘以较高容量的桶数（包括无限桶）的总和。

如果小于 w，您就知道需要将桶装得更高，因此特别是所有容量较低的桶都将被装满。删除它们，从 w 中删除它们的容量总和，您就完成了本次迭代，n'=n/2。

另一方面，如果总和大于 w，则您知道没有桶将被填充到中位数容量或更高。因此，可以移除所有具有较高容量的桶，并将它们的数量添加到无限桶的数量中。w 保持不变。再次，n'=n/2，我们就完成了。

为了保持简短，跳过了一些简单的细节（特别是如何处理许多桶具有完全相同容量的情况）。一旦您知道了正确的水位，您还需要在最后进行一些清理，以便为每个“无限”（即非满）桶设置它。