发电厂-解决O(nlogn)中的问题

Question

我在考试中遇到了以下问题:某一发电厂需要煤才能运行，因此它订购了n交付，每一次交付的信息(吨数)都存储在A列表中。交付的煤炭储存在0、1、.号的仓库中。(没有给出它们的确切数目)。每个仓库的容量(以吨为单位)与T号( T>=A[i] for i=0,1,...,n-1)相同。储存煤有几条规则。煤是分不开的，也就是说，每批货物只能分配给一个仓库。另外，我们总是尽可能少地把煤放到仓库里。问题是如何找到存储最后一次(n-1)交付的仓库号。

例如：

A = [1, 6, 2, 10, 8, 3, 1]
T = 10

答案是0。

解决这个问题的O(n^2)是很明显的，但是我不知道如何在O(nlogn)中解决这个任务，这就是你能得到最大的复杂度。有什么想法吗？

Answer 1

我想最好的方法是按照非空仓库的剩余容量对数组进行排序。二进制搜索将在O(logN)中找到可能的仓库，因为所有大于Ai的叶子都是候选的。然而，在最坏的情况下，我认为不可能满足第二个条件(必须选择最小的仓库)在O(N)以下。