algorithm - 如何解决数组之间的最高组合总数？

Question

1. 有 3 个数组:miners、minersLevel、oresMined
2. 每个矿工只能开采一次矿石，但只能在矿工级别或以下
3. 矿工最多可以开采多少矿石？

miners = [10, 1, 7, 9, 6, 1, 5, 3, 2, 3]
minersLevel = [9, 2, 4, 5, 1, 9, 2, 4, 2, 7]
oresMined = [7, 9, 9, 4, 8, 7, 10, 4, 10, 8]


output: 96
internally represented as [10, 8, 10, 10, 10, 8, 10, 10, 10, 10] = 96

Q)我将如何解决这个问题，使速度(纳秒)尽可能快，我可以在每个矿工之间进行蛮力检查，然后检查每个级别并跟踪迄今为止开采的最高矿石，然后在结束，但这将是 O(n^2) 并且太慢了。

我认为另一种极端情况是找到最低的 minersLevel 到最高的 oresMined，如果 minersLevel = 1 和 OresMined = 10，那么默认情况下最大值为 100，但我将如何处理其他级别？

请注意，排序也会花费太多时间。数组的长度通常为 10，元素值从 1 到 10。

Answer 1

将代码放入 Python 中:

miners = [10, 1, 7, 9, 6, 1, 5, 3, 2, 3]
minersLevel = [9, 2, 4, 5, 1, 9, 2, 4, 2, 7]
oresMined = [7, 9, 9, 4, 8, 7, 10, 4, 10, 8]

sum = 0
oreArray = [0]*len(miners)
for i in range(len(miners)):
    highestOre = -1
    for j in range(len(minersLevel)):
        if(minersLevel[j] <= miners[i]):
            # we can mine this ore
            if(oresMined[j] > highestOre):
                highestOre = oresMined[j]
    sum = sum + highestOre
    oreArray[i] = highestOre

print sum,oreArray

这给出了你在 O(n^2) 时间内给出的答案。

您可以按如下方式在 O(n) 时间内完成此操作:

m = max(max(minersLevel),max(miners))
# Create B so B[i] will store the highest value ore for a mine of level i
B = [0] * (m+1) 
for i,v in enumerate(oresMined):
    lev = minersLevel[i] # Level of the mine
    B[lev] = max(B[lev],v)
# Now create C array so C[i] stores the highest value ore for a mine of level i or less
highestOre = 0
C=[]
for v in B:
    highestOre = max(highestOre,v)
    C.append(highestOre)
# Now go through miners and find optimum result
oreArray = []
sum = 0
for lev in miners:
    v = C[lev]
    sum += v
    oreArray.append(v)

print sum,oreArray

想法是创建两个辅助数组。

1. B[i] 将存储 i 级矿山中值(value)最高的矿石
2. C[i] 存储 i 级或以下矿山的最高值(value)矿石

一旦我们有了这些数组，我们就可以简单地遍历矿工并为每个人查找最佳答案。