Как решить наибольшую суммарную сумму между массивами?

Question

1. Существует 3 массива: шахтеры, уровень шахтеров, руды. Шахты
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) и будет слишком медленным.

Еще один крайний случай, который я подумал, - это найти самые низкие майнерыLevelк наивысшему 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
2. C [i] хранит руду с наибольшей ценностью для шахты уровня i или меньше

Как только мы получим эти массивы, мы можем просто пройтись по майнерам и найти лучший ответ для каждого.