7.6. Задача «Максимальный оклад»

Авторы: Алексей Толстиков, Александр Куликов

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

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

Ключевые вопросы статьи

• Почему обычная сортировка по убыванию не работает для составления максимального числа?
• Как сравнивать строки чисел, чтобы результат был действительно максимальным?
• Какие ошибки чаще всего возникают при реализации таких задач — и как их избежать?

Вопрос на собеседованииВопрос на собеседовании

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

Вспомните алгоритм для этой задачи, который работает с однозначными числами.

LargestConcatenate(Numbers):
    yourSalary = "" # пустая строка
    while Numbers is not empty:
        maxNumber = -infinity
        for each number in Numbers:
            if number >= maxNumber:
                maxNumber = number
        yourSalary = yourSalary + maxNumber # добавляем число в конец
        Numbers.remove(maxNumber) # удалить из рассмотрения число maxNumber
    return yourSalary

Такой алгоритм не всегда будет приводить к самой большой зарплате: например, при вводе из двух целых чисел 23 и 3 он выдаст 233, в то время как самое большое число — 323.

Не беспокойтесь, чтобы получить самую большую зарплату, вам всего лишь нужно заменить строку

if number >= maxNumber:

на следующую:

if IsBetter(number, maxNumber):

Для надлежаще реализованной функции IsBetter нужно учесть порядок цифр и их количество. Функции IsBetter(first, second) должна возвращать булеву величину сооветствующую ответу на вопрос: нужно ли ставить число first раньше числа second. Например, IsBetter(3, 23) выдаст True.

• Входные данные: Первая строка ввода содержит целое число . Вторая строка содержит целые числа .
• Выходные данные: Самое большое возможное число, которое состоит из .
• Ограничения: ; для всех .

Пример 1Пример 1

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

Пример 2Пример 2

Ввод состоит только из однозначных чисел, поэтому алгоритм выше выдаёт правильный ответ.

Пример 3Пример 3

Тем не менее алгоритм LargestConcatenate (неверный) в этом случае приводит к правильному результату — ещё одно напоминание, что всегда стоит проверять правильность жадных алгоритмов!

Что дальшеЧто дальше

Теперь вы знаете, как применять жадную стратегию не только к числам, но и к строкам. Вы научились сравнивать строки так, чтобы получить максимальное число, — и поняли, что простой порядок убывания не всегда работает. Эта задача — отличный пример того, как важно выбрать правильный критерий сравнения, даже если идея кажется простой.

Далее — подведение итогов. Вы вспомните, какие приёмы жадных алгоритмов вы освоили, в чём их сила и в чём ограничения.

Ключевые выводы статьи

• В некоторых задачах важно уметь сравнивать строки нестандартным способом — не по алфавиту, а по результату объединения.
• Простая сортировка не всегда даёт правильный результат: нужно чётко задать правило, по которому элементы упорядочиваются.
• Жадные стратегии применимы и к строкам, но требуют особенно внимательной формулировки критерия выбора.