Лексикографія#9591

Лексикографія (Розбір)

У задачі слід розподілити задані $n \cdot l$ n \cdot l літери по $n$ словам довжиною $l$ , відсортованим лексикографічно, так щоб $k$ -те слово було лексикографічно мінімально можливим.

Лексикографічний порядок слів визначається посимвольно зліва направо. Тому, щоб мінімізувати $k$ -те слово, потрібно як можна раніше (в перших позиціях) поставити до нього найменші можливі літери, не порушуючи сортування всіх слів.

Це приводить до наступного жадного алгоритму:

Відсортуємо всі літери вхідного рядка за зростанням.
Будемо будувати двовимірний масив символів
$v [1.. n] [1.. l],$
v[1 .. n][1 .. l],
де кожен рядок — окреме слово.
Заповнюємо масив по стовпцях зліва направо, оскільки саме стовпці відповідають за позиції в словах і впливають на лексикографічний порядок.

Заповнення першого стовпця

У перший стовпець роздаємо літери тільки рядкам з номерами від $1$ до $k$ , використовуючи $k$ найменших доступних літер.
Ці літери розміщуються зверху вниз, щоб зберігався лексикографічний порядок.
Рядки з номерами $k + 1, ..., n$ k + 1, ..., n на цьому етапі не заповнюються, оскільки вони не впливають на мінімальність $k$ -го слова.

Таким чином, ми гарантуємо, що перший символ $k$ -го слова мінімальний.

Заповнення наступних стовпців

Для кожного стовпця $j = 2, 3, ..., l$ j = 2, 3, ..., l:

Серед рядків $1, ..., k$ 1, ..., k знаходимо мінімальний індекс $pt$ , такий що рядки $pt$ і $k$ збігаються на всіх попередніх стовпцях $1, ..., j - 1$ 1, ..., j - 1.
Це множина рядків $[pt, k]$ — всі слова, які на поточному префіксі не відрізняються від $k$ -го і тому зобов'язані залишатися не більшими за нього.
У стовпці $j$ роздаємо найменші доступні літери тільки рядкам з номерами від $pt$ до $k$ , зверху вниз.
Повторюємо процес, поки всі $l$ символів $k$ -го слова не будуть зафіксовані.

Заповнення інших клітинок

Після того як $k$ -те слово повністю побудовано:

Всі залишилися літери можна розподілити довільно, не порушуючи лексикографічного сортування.
Наприклад, можна послідовно заповнювати масив по рядкам зверху вниз і зліва направо залишилися літерами у відсортованому порядку.

Коректність

У кожному стовпці ми мінімізуємо поточний символ $k$ -го слова.
Ми видаємо однакові або незростаючі літери всім словам, які збігаються з ним за префіксом, тому порядок слів не порушується.
Після завершення $k$ -го слова подальші дії не можуть зробити його більшим.

Отже, отримане $k$ -те слово є лексикографічно найменшим.

Приклад

Розглянемо наступний тест

6 3 6
fgahhfgaaebdcbbebc

Тут потрібно скласти $6$ слів довжини $3$ , використовуючи всі літери, так щоб $6$ -те слово в лексикографічно відсортованому списку було мінімальним.

Відсортуємо рядок вхідних літер:

aaabbbb cc d ee f f g g hh

aaabbbbccdeeffgghh

Всього $18 = 6 \cdot 3$ 18 = 6 \cdot 3 літер, що відповідає розміру таблиці $6 \times 3$ 6 × 3.

Стовпець 1. Заповнюємо перший стовпець літерами зверху вниз від першої до шостої рядка, оскільки саме вона нас цікавить.

Стовпець 2. Тепер розглянемо рядки, чий префікс збігається з префіксом $6$ -ї рядка. Префікс $6$ -ї рядка після першого стовпця є " $b$ ". Збігатимуться будуть рядки $4, 5$ і $6$ . Мінімальний номер такого рядка $pt = 4$ pt = 4.

У другому стовпці роздаємо мінімальні доступні літери рядкам з номерами від $4$ до $6$ .

Стовпець 3. Знову шукаємо рядки, чий префікс збігається з " $b c$ " (після заповнених двох стовпців). Збігатимуться будуть рядки $5$ і $6$ . Мінімальний номер такого рядка $pt = 5$ pt = 5. Роздаємо мінімальні доступні літери рядкам з номерами від $5$ до $6$ . Тепер $6$ -те слово повністю сформовано і дорівнює " $b c d$ ".

Заповнення залишилися літер

Після фіксації $6$ -го слова залишилися літери можна розподілити довільним коректним чином. Наприклад, заповнимо таблицю по рядкам зверху вниз і зліва направо залишилися літерами у лексикографічному порядку.

Розглянемо перший тест

3 2 2
abcdef

Відсортуємо вхідний рядок літер:

ab c d e f

Нам слід заповнити матрицю з $3$ слів по $2$ літери кожне, лексикографічно мінімізувавши при цьому $2$ -е слово.

Спочатку заповнюємо перший стовпець літерами зверху вниз, тільки для рядків з $1$ -ї по $2$ -ю, оскільки саме вони впливають на мінімальність другого слова.

Далі переходимо до другого стовпця. Його слід заповнювати, починаючи з найранішої рядка, префікс якої збігається з префіксом $2$ -ї рядка. У цьому випадку такою рядком є сама $2$ -я рядок, тому $pt = 2$ pt = 2. Заповнюємо другий стовпець літерами від рядка номер $pt$ до $2$ -ї рядка.

Після цього залишилися літери розподіляємо у лексикографічному порядку по рядках зверху вниз і зліва направо, що завершує побудову коректної відповіді.

Реалізація алгоритму

Читаємо вхідні дані.

cin >> n >> l >> k;
cin >> s;

Відсортуємо літери вхідного рядку. Поточною оброблюваною буквою буде $s [p os]$ .

pos = 0;
sort(s.begin(), s.end());

Оголосимо матрицю результату $v$ , що складається з $n$ рядків і $l$ стовпців, де кожен рядок відповідає одному слову довжини $l$ .

vector<string> v(n, string(l, ' '));

Будемо розподіляти літери по стовпцю з номером $j$ , заповнюючи рядки з номерами від $pt$ до $k - 1$ k - 1 включно (нумерація рядків починається з нуля).

int pt = 0;
for (j = 0; j < l; j++)
{
  for (i = pt; i < k; i++)
    v[i][j] = s[pos++];

Рухаємо вказівник $pt$ вперед $(pt + +)$ (pt++) до тих пір, поки $j$ -ий символ $(k - 1)$ (k - 1)-ої рядка не співпаде з $j$ -им символом рядку номер $pt$ . В результаті $pt$ вказує на рядок з найменшим номером, яка на поточному кроці збігається з префіксом рядку $k - 1$ k - 1.

  while (v[pt][j] != v[k - 1][j]) pt++;
}

Після цього заповнюємо залишилися осередки матриці. Для цього послідовно проходимо по рядках зверху вниз і по стовпцях зліва направо, розподіляючи залишилися літери.

for (i = 0; i < n; i++)
for (j = 0; j < l; j++)
  if (v[i][j] == ' ') v[i][j] = s[pos++];

Виводимо відповідь.

for (i = 0; i < n; i++)
  cout << v[i] << endl;