Будем идти по массиву с конца. Понятно, что раз мы хотим сделать последовательность неубывающей, последнее число менять не стоит. Из предпоследнего числа хочется удалить несколько цифр так, чтобы оно стало максимально возможным, но не большим последнего. И так далее.
Как по данным числам a, b удалить несколько цифр из числа a, чтобы оно стало максимально возможным, не большим b?
- Если длина a меньше длины b, ничего делать не надо;
- Если нет, то заметим факт: чем больше общий префикс a, b после удаления цифр, тем число a больше;
- Переберем длину этого общего префикса prefix от 0 до |b|, пройдем по числу a, удаляя цифры, не относящиеся к общему префиксу. Пусть индекс последней цифры общего префикса в числе a — index;
- После этого нужно сделать две вещи:
- проверить, что минимальное число, которое можно получить из a с таким префиксом, не больше b;
- построить, собственно, максимальное число, не большее b.
- Для проверки этих двух пунктов предподсчитаем массив next[i][d] = min{j > i|a[j] = d}
- Теперь, чтобы проверить, что минимальное число, которое можно получить из a с перебранным префиксом, будет не больше b, переберем следующую его цифру digit после общего префикса (от 1 до b[prefix] - 1) и проверим, что |a| - next[index][digit] > = |b| - prefix (i — индекс в числе a, ) — то есть что взяв эту цифру мы сможем набрать цифр для получения числа такой же длины, что и b (число будет заведомо меньше по построению);
- Чтобы построить максимальное число с зафиксированным общим префиксом и не больше b, действуем так же — перебираем первую цифру после общего префикса от b[prefix] - 1 до 1, а все остальные от 9 до 1, а потом проверяем то же условие — то есть строим наше число жадно;
- Также стоит не забыть про случай, когда ни один из префиксов не подошел — тогда надо сделать число a максимальным длиной на один меньше, чем b — это делается таким же алгоритмом, как и предыдущие два пункта.
В итоге, наш алгоритм выглядит следующим образом:
- Перебрать числа массива в обратном порядке;
- Рассматривая два соседних числа массива a, b, предподсчитать массив next[i][d];
- Перебрать длину общего префикса prefix от 0 до |b|;
- Проверить одно условие существования ответа, а после построить ответ
- Заменить a в массива на только что полученное число и продолжить алгоритм
Итоговая асимптотика нашего алгоритма — O(
), что вполне укладывается в лимит по времени.