6.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.

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

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

Пример 1

Ввод	Вывод
2 21 2	221

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

Пример 2

Ввод	Вывод
5 9 4 6 1 9	99641

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

Пример 3

Ввод	Вывод
3 23 39 92	923923

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