Задание 26
тема 2 из 5

Сортировка и жадный выбор

Сортировка располагает данные по возрастанию или убыванию ключа, а жадный выбор после неё на каждом шаге берёт лучший из доступных объектов. Так решают задание 26: больше всего файлов на диск входит, если брать их от меньшего к большему, а самую длинную матрёшку из коробок собирают от большей коробки к меньшей. В Python сортирует функция sorted, но на экзамене нужно знать и простые методы сортировки, и двоичный поиск.

Главная тема в задании26Реже в задании27На карте навыков

Сортировка и жадный выбор

Сортировка — расстановка элементов по возрастанию или убыванию ключа. Жадный алгоритм на каждом шаге делает выбор, лучший в данный момент, и не пересматривает его.

  • sorted(a) — новый список по возрастанию, reverse=True — по убыванию, key — ключ, кортеж в ключе — несколько ключей.
  • Больше всего предметов в пределе суммы: сортируйте по возрастанию и берите, пока сумма не больше предела.
  • Самый большой предмет в таком наборе: замените последний взятый на самый большой, который ещё помещается.
  • Самая длинная цепочка с разницей хотя бы dd: сортируйте по убыванию и берите каждый элемент, который меньше последнего взятого хотя бы на dd.
  • Больше всего мероприятий без пересечений: сортируйте по времени окончания и берите каждое, которое начинается не раньше конца предыдущего.

Сортировка по одному и нескольким ключам

sorted(a) возвращает новый список по возрастанию, a.sort() сортирует сам список a. Параметр reverse=True даёт порядок по убыванию. Ключ сортировки — значение, по которому сравнивают элементы. Его задаёт параметр key: sorted(words, key=len) упорядочивает слова по длине.

Если ключ — кортеж, записи сравниваются по первому числу, при равенстве — по второму, и так далее. key=lambda p: (-p[1], p[0]) упорядочивает пары по убыванию второго числа, а при равенстве — по возрастанию первого. Сортировка в Python устойчивая: записи с равными ключами сохраняют исходный порядок.

Пример

Результаты: Оля — 85, Петя — 92, Аня — 85, Ваня — 70. Расставьте учеников по убыванию балла, а при равном балле — по алфавиту.

  1. 1.Ключ (-p[1], p[0]): минус перед баллом даёт порядок по убыванию.
  2. 2.Первый — Петя с 92 баллами. У Ани и Оли по 85, второй ключ ставит Аню раньше.
  3. 3.Последний — Ваня с 70 баллами.

Ответ: Петя, Аня, Оля, Ваня

Метод пузырька

Метод пузырька проходит по массиву слева направо и сравнивает соседние элементы. Если левый больше правого, их меняют местами. После первого прохода самый большой элемент оказывается в конце, после второго — второй по величине на предпоследнем месте. Массиву из nn элементов хватает n−1n - 1 проходов, и каждый следующий проход на один элемент короче.

Пример

Отсортируйте методом пузырька массив 5, 1, 4, 2. Сколько обменов будет сделано?

  1. 1.Проход 1: 5 и 1 — обмен, 5 и 4 — обмен, 5 и 2 — обмен. Массив 1, 4, 2, 5.
  2. 2.Проход 2: 1 и 4 — без обмена, 4 и 2 — обмен. Массив 1, 2, 4, 5.
  3. 3.Проход 3: 1 и 2 — без обмена. Обменов всего 3+1=43 + 1 = 4.

Ответ: 1, 2, 4, 5; 4 обмена

Сортировка выбором и вставками

Сортировка выбором: найдите наименьший элемент массива и поменяйте его с первым. Затем найдите наименьший среди элементов со второго и поменяйте его со вторым, и так далее. На шаге kk на место kk встаёт наименьший из оставшихся.

Сортировка вставками: левая часть массива всегда упорядочена. Очередной элемент сдвигают влево, пока слева от него стоит больший, и вставляют на своё место в левой части.

Пример

Отсортируйте выбором массив 5, 1, 4, 2.

  1. 1.Шаг 1: наименьший элемент 1, меняем его с 5. Массив 1, 5, 4, 2.
  2. 2.Шаг 2: среди 5, 4, 2 наименьший 2, меняем его с 5. Массив 1, 2, 4, 5.
  3. 3.Шаг 3: среди 4, 5 наименьший 4, он уже на месте.

Ответ: 1, 2, 4, 5

Методы сортировки

МетодИдеяЧисло сравнений для n элементов
Пузырёкобмен соседей, большие уходят в конецоколо n2/2n^2 / 2
Выборнаименьший из оставшихся — на очередное местооколо n2/2n^2 / 2
Вставкиочередной элемент — на место в упорядоченной частидо n2/2n^2 / 2
Слияниеотсортировать половины и слить ихоколо nlog⁡2nn \log_2 n
Быстрая (QuickSort)разделить по опорному элементу на меньшие и большиев среднем около nlog⁡2nn \log_2 n, в худшем случае около n2/2n^2 / 2

Сортировка слиянием и быстрая сортировка

Сортировка слиянием делит массив пополам, сортирует каждую половину тем же способом и сливает их. При слиянии двух упорядоченных списков сравнивают их первые элементы, меньший переносят в результат, и так до конца. Слияние проходит каждый элемент один раз.

Быстрая сортировка выбирает опорный элемент и раскладывает массив на две части: меньшие опорного и не меньшие. Каждую часть сортируют тем же способом. Для 10 000 элементов такие методы делают около 130 тысяч сравнений, а пузырёк — около 50 миллионов.

Пример

Слейте упорядоченные списки 2, 7, 9 и 1, 3, 8.

  1. 1.Первые элементы 2 и 1: переносим 1. Затем 2 и 3: переносим 2.
  2. 2.7 и 3: переносим 3. 7 и 8: переносим 7. 9 и 8: переносим 8.
  3. 3.Второй список кончился, остаток первого (9) переносим целиком.

Ответ: 1, 2, 3, 7, 8, 9

Двоичный поиск

Двоичный поиск находит значение в упорядоченном массиве. Сравните искомое число со средним элементом участка. Если среднее меньше, ищите в правой половине, если больше — в левой. Каждое сравнение вдвое уменьшает участок, поэтому для nn элементов хватает около log⁡2n\log_2 n сравнений: для 1000 элементов — 10. Линейный поиск просматривает элементы по очереди и в худшем случае делает nn сравнений.

Пример

Найдите двоичным поиском число 23 в массиве 3, 8, 11, 15, 23, 31, 42. Сколько средних элементов будет проверено?

  1. 1.Участок с номерами от 0 до 6, средний номер 3: элемент 15 меньше 23, ищем справа, номера от 4 до 6.
  2. 2.Средний номер 5: элемент 31 больше 23, ищем слева, участок из одного номера 4.
  3. 3.Номер 4: элемент 23 найден. Проверено три элемента.

Ответ: номер 4, три проверки

Жадный выбор: больше всего предметов в пределе суммы

Чтобы в предел SS (объём диска, кузова) вошло больше всего предметов, отсортируйте их по возрастанию и берите подряд, пока сумма не больше SS. Это жадный выбор: каждый раз берётся самый маленький из оставшихся. Он верен, потому что любой набор из kk предметов весит не меньше, чем kk самых маленьких. Если kk самых маленьких не входят, не войдут и никакие kk предметов.

Пример

Свободно 90 Кбайт, файлы весят 50, 20, 35, 10 и 40 Кбайт. Сколько файлов больше всего можно записать?

  1. 1.По возрастанию: 10, 20, 35, 40, 50.
  2. 2.Сумма: 10, 30, 65. Следующий файл даёт 65+40=105>9065 + 40 = 105 > 90, цикл останавливает break.
  3. 3.Вошло 3 файла.

Ответ: 33

Самый большой предмет в наибольшем наборе

Второй вопрос задания 26: какой самый большой предмет может войти в набор из наибольшего числа kk предметов. Остальные k−1k - 1 предметов выгодно взять самыми маленькими. Их сумма rest — сумма жадного набора без последнего взятого. Ответ — самый большой предмет xx из оставшихся (последний взятый тоже подходит), для которого rest + x <= S.

Пример задания

Открытый банк ФИПИ

Илье необходимо перенести файлы с одного компьютера на другой при помощи внешнего жесткого диска.
Объём диска может быть меньше, чем требуется для переноса всех файлов за один раз. Свободный объём на диске и размеры файлов известны.
По заданной информации об объёме файлов на компьютере и свободном объёме на диске определите максимальное число файлов, которые могут быть перенесены за один раз на внешний жёсткий диск, а также максимальный размер файла, записанного на этот диск, при условии, что перенесено наибольшее возможное число файлов.
Входные данные:
В первой строке входного файла находятся два числа: S — размер свободного места на диске (натуральное число, не превышающее 100 000) и N — количество файлов, которые надо перенести (натуральное число, не превышающее 10 000). В следующих N строках находятся значения объёмов указанных файлов (все числа натуральные не превышающие 100), каждое в отдельной строке.
Выходные данные:
Запишите в ответе два числа: сначала наибольшее число файлов, которые могут быть перенесены на внешний жёсткий диск за один раз, затем максимальный размер перенесённого файла, при условии, что перенесено наибольшее возможное число файлов. Если вариантов переноса несколько, выберите тот, при котором будет перенесён наибольший файл.
Пример входного файла:
100 4 
80
30
50
40.
При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов: 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар — 50, поэтому ответ для приведённого примера: 2 50.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

44345_26.txt

Самая длинная цепочка: матрёшка

Коробку можно вложить в другую, если её сторона меньше хотя бы на dd. Чтобы цепочка вложенных коробок была самой длинной, отсортируйте стороны по убыванию. Возьмите самую большую коробку, затем идите по списку и берите каждую коробку, которая меньше последней взятой хотя бы на dd.

Жадная цепочка на каждом месте держит самую большую возможную коробку: первая — самая большая из всех, а каждая следующая — самая большая из тех, что влезают в предыдущую. Поэтому эта цепочка самая длинная, и её последняя коробка — самая большая из возможных последних. Оба ответа дают одна сортировка и один проход.

Пример задания

Открытый банк ФИПИ

Задание выполняется с использованием прилагаемых файлов.

В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки – подарок упаковывается в одну из коробок, та, в свою очередь, в другую коробку и т.д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 9 единиц меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой из этих коробок. Размер подарка позволяет поместить его в самую маленькую коробку.

Входные данные
В первой строке входного файла находится число N – количество коробок в магазине (натуральное число, не превышающее 10 000). В следующих N строках находятся значения длин сторон коробок (все числа натуральные, не превышающие 10 000), каждое – в отдельной строке.
Запишите в ответе два целых числа: сначала наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком наборе.

Типовой пример организации данных во входном файле
5
43
40
32
40
30

Пример входного файла приведён для пяти коробок и случая, когда минимальная допустимая разница между длинами сторон подходящих коробок составляет 3 единицы. При таких исходных данных условию задачи удовлетворяют наборы коробок с длинами сторон 30, 40 и 43 или 32, 40 и 43 соответственно, т.е. количество коробок равно 3, а длина стороны самой маленькой коробки равна 32.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.

1_26.txt

Заявки на зал: выбор по времени окончания

Мероприятия не должны пересекаться, но одно может начаться в ту же минуту, когда закончилось другое. Чтобы провести больше всего мероприятий, отсортируйте заявки по времени окончания. Берите каждую заявку, которая начинается не раньше конца последней взятой. Раннее окончание оставляет больше времени для следующих.

Наибольший перерыв между двумя последними мероприятиями: первые k−1k - 1 мероприятий жадный выбор заканчивает как можно раньше. Последним берут заявку с самым поздним началом среди тех, что начинаются не раньше этого конца. Перерыв — её начало минус конец предпоследнего.

Пример

Заявки (начало и конец в минутах): 10–40, 30–50, 45–60, 40–45, 55–90, 60–70, 75–80. Сколько мероприятий больше всего можно провести и какой наибольший перерыв между двумя последними?

  1. 1.По времени окончания: 10–40, 40–45, 30–50, 45–60, 60–70, 75–80, 55–90.
  2. 2.Берём 10–40, 40–45, 45–60, 60–70, 75–80. Заявки 30–50 и 55–90 начинаются раньше конца взятой. Мероприятий 5.
  3. 3.Предпоследнее кончается не раньше 70. Позже 70 начинается только 75–80, перерыв 75−70=575 - 70 = 5.

Ответ: 5 мероприятий, перерыв 5 минут

Потренируйте навык

Все задания на этот навык

Решать