1

Задача вместить некоторое количество вещей в коробки. В одну коробку можно вместить не более 2 вещей. Вещи заданы списком из чисел, обозначающих их вес. Максимальный вес, который можно положить в коробку задан вторым параметром. То есть, если дано ([5, 1, 4, 2, 3], 6), то нам нужно 3 коробки, чтобы вместить все вещи, максимум по 6 кило в коробку (например вот так 1: 5+1, 2: 4+2, 3: 3). Решение у меня есть такое. Но как решить с помощью O(NlogN)?

def count(t,x):
  
  newT = sorted(t[:])
  counter = 0

  while len(newT) > 0:
    i = 0
    weight = x - newT[i]
    sec = max((i for i in newT if i <= weight), default=0) 
    newT.remove(newT[i])
    if sec in newT: newT.remove(sec)
    counter += 1
  return counter
    
    if __name__ == "__main__":
      print(count([7, 10, 6, 7, 8], 11)) #5
      print(count([5, 1, 4, 2, 3], 6)) #3
      print(count([1, 3, 5, 999999999, 10000000000, 1000000000], 10000000000)) #4
      print(count([1, 2, 3, 4, 5], 5)) #3

2 ответа 2

2

Есть такая фраза - "Не знаешь как решить задачу - отсортируй данные"

Отсортировали по убыванию. O(nlogn)

Один индекс идёт слева, второй справа.

Для каждого большого веса (индекс слева) находим максимальный, который можно добавить (правый индекс идёт влево), если он есть, и делаем пару. O(n)

1

В общем, получилось у меня вот такое решение в итоге

def countBoxes(items,weight):
  items.sort(reverse=True)
  n = len(items)
  boxCounter = 0
  small = n-1
  big = 0 
  while big <= small:
    boxCounter+=1
    if weight - items[big] >= items[small]:
      small -= 1
    big += 1

  return boxCounter

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.