Перед вами, возможно, самая важная задача в книге. В качестве последнего вопроса на собеседовании будущий начальник даёт вам пять бумажек с одним числом на каждой и просит составить из них самое большое число. Получившееся число — ваша зарплата, поэтому мотивация, чтобы решить эту задачу, зашкаливает.
Вспомните алгоритм для этой задачи, который работает с однозначными числами.
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
?
- Входные данные: Первая строка ввода содержит целое число $n$. Вторая строка содержит целые числа $a_1, \dotsc, a_n$.
- Выходные данные: Самое большое возможное число, которое состоит из $a_1, \dotsc, a_n$.
- Ограничения: $1 \le n \le 100$; $1 \le a_i \le 10^3$ для всех $1 \le i \le n$.
Пример 1
Ввод | Вывод |
---|---|
2 21 2 | 221 |
Обратите внимание, что в этом случае приведённый выше алгоритм также выдаёт неправильный ответ 212.
Пример 2
Ввод | Вывод |
---|---|
5 9 4 6 1 9 | 99641 |
Ввод состоит только из однозначных чисел, поэтому алгоритм выше выдаёт правильный ответ.
Пример 3
Ввод | Вывод |
---|---|
3 23 39 92 | 923923 |
Тем не менее алгоритм LargestConcatenate
(неверный) в этом случае приводит к правильному результату — ещё одно напоминание, что всегда стоит проверять правильность жадных алгоритмов!