Василько і комп'ютер (Editorial)

Автор: Костянтин Денисов

Роздробник: Павло Цікалишин

Розбір підготовано: Костянтин Денисов

Можна розв'язувати жадібно: робити перший підмасив якомога довшим, потім другий якомога довшим, і т.д.

Чому так можна: припустимо, існує оптимальне розбиття, де перший підмасив закінчується раніше, ніж це можливо. Нехай другий підмасив починається з елемента $x$. Якщо додавання $x$ в кінець першого підмасиву не ламає можливість відсортувати його стеком, то ми можемо просто "перекласти" $x$ з початку другого підмасиву в кінець першого. Другий підмасив при цьому стає коротшим, але він все одно відсортовуваний (бо ми лише забрали з нього перший елемент). Отже завжди існує оптимальне розбиття, в якому перший підмасив максимально довгий. Те саме міркування працює для кожного наступного підмасиву.

Тому достатньо йти зліва направо і додавати елементи в поточний підмасив, доки це можливо; коли стає неможливо — робимо розріз і починаємо новий.

Ми будуємо один підмасив зліва направо і симулюємо, як би працювало сортування стеком. Коли ми кладемо елементи в стек, іноді ми змушені викидати деякі зі стеку у вихідну послідовність: якщо прийшов новий елемент $x$, який більший за верхівку стека, то цю верхівку вже не можна тримати далі, бо інакше $x$ опиниться над меншим елементом і ми ніколи не зможемо отримати відсортований вихід.

Тому правило таке: поки top < x, ми викидаємо $top$ зі стека. Серед усіх викинутих значень запам'ятовуємо найбільше $m$. Коли прийдемо до випадку top > x, то в цьому випадку вже не можна класти верхівку стеку до масиву, бо тоді новий елемент $x$ точно не буде стояти на своїй позиції.

$m$ — це фактично найбільше число, яке ми вже викинули зі стека у цьому підмасиві. Тобто у фінальній відсортованій послідовності воно вже стоїть десь зліва, і ми вже не можемо поставити перед ним щось менше.

Якщо в якийсь момент приходить елемент $x$ та виконується x<m, то все: поточний підмасив вже неможливо відсортувати стеком. Чому: число $m$ уже "пішло" у вихід і мусить стояти до $x$ у фінальній послідовності, але x<m, отже порядок буде неправильний і це вже не виправити ніякими майбутніми діями зі стеком.

У такому випадку ми зобов'язані розрізати масив перед $x$ і почати новий підмасив: очищаємо стек, скидаємо $m$ і збільшуємо лічильник частин.

В інших випадках (top >= m) нескладно збагнути, що можна просто перекинути весь стек у кінцевий масив, щоб він був відсортованим.

Складність. Кожен елемент один раз заходить у стек і не більше одного разу виходить зі стека, тому час $O(n)$, пам'ять $O(n)$.