Изменения

Перейти к: навигация, поиск

Участник:Irdkwmnsb

322 байта добавлено, 21:24, 6 января 2021
fixes
* Двигаясь снизу вверх будем рассматривать подмножества.
** Если мы можем дописать в текущее подмножество минимальный элемент из удалённых, то мы нашли следующее разбиение и идти дальше вверх не нужнозавершить цикл.** Если дописать не можем, значит, либо нужно укоротить и заменить какой то элемент в текущем подмножестве, либо перейти к следующему подмножеству. Будем идти справа налево и рассамтривать рассматривать элементы:*** Если мы можем заменить текущий элемент минимальным удалённым {{---}} мы нашли следующее разбиение, завершаем оба проходацикла и выполняем алгоритм дальше. Стоит отметить, что нельзя перезаписывать последний элемент в подмножестве, иначе мы не сможем дописать минимальный хвост после этого подмножества {{---}} в удалённых будет элемент меньше текущего и мы не сможем дописать правильный хвоствыписать удаленные элементы так, чтобы получилось корректное разбиение.*** Если заменить не можемтекущий элемент каким то из удалённых нельзя, то его нужно следует удалитьи этот.
* Допишем лексикографически минимальный хвост подмножеств из оставшихся удалённых элементов.
| ||^|| ||Удалили элемент 5.
|-
| || || ||usedУдалённые элементы
|}
|^|| || ||Удалили элемент 4. Так как он является последним в подмножестве, то мы не можем заменить его на другой.
|-
|5|| || ||usedУдалённые элементы
|}
| || || ||^||Дополнили первое подмножество элементом 4
|-
|5|| || || ||usedУдалённые элементы
|}
|style="background:#FFCC00"|5|| || || ||Дописали лексикографически минимальный хвост
|-
| || || || ||usedУдалённые элементы
|}
8
правок

Навигация