Задачи
September 19

Задача. Lifeboats

Задача. Дан массив arr, где arr[i] - вес i-го человека. А также у вас есть неограниченное количество лодок, где каждая лодка может нести максимальный вес limit. Каждая лодка перевеозит не более 2х человек одновременно, если только сумма веса этих людей не превышает предела.

Необходимо посчитать минимальное количество лодок, чтобы перевезти каждого человека.

Примеры:

  1. arr = [1,2], limit = 3 Output: 1
  2. arr = [3,2,2,1], limit = 3 Output: 3

Разбор

Воспользуемся методом 2х указателей:

  1. Отсортируем исходный массив.
  2. Начальная позиция: 1й указатель - 1й элемент массива, 2й указатель - последний элемент массива.
  3. В цикле проверяем следующие варианты:
    - Указатели соот-т одному элементу: увеличиваем результирующий счетчик, выходим из цикла.
    - Проверяем сумму двух элементов, если она меньше лимита, то также увеличиваем результат, меняем указатели и переходим к след.итерации цикла.
    - Сумма больше лимита, значит сажаем человека с большим весом в лодку одного, увеличиваем 2й указатель и переходим к след.итерации.
  4. Возвращаем результат.

Реализация

Play-test

https://dotnetfiddle.net/tMZFG9