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

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

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

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

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

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

1if number >= maxNumber:

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

1if IsBetter(number, maxNumber):
2

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

💡 Остановитесь и подумайте:
Как бы вы реализовали IsBetter?

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

Пример 1

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

Пример 2

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

Пример 3

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