Ctrl K

Обменять в столбцах, чтобы оба ряда росли

Сложная
Даны два ряда чисел одинаковой длины: top и bottom. Их можно представить как таблицу из двух строк, где i-й столбец — пара top[i], bottom[i]. За одно действие можно выбрать столбец и поменять местами его верхнее и нижнее число. Верните наименьшее число действий, после которых оба ряда будут строго возрастающими. Гарантируется, что это возможно.
Пример 1
top=[1, 6, 3, 8], bottom=[2, 2, 7, 9] → 1

Меняем числа в столбце 1: верхний ряд становится [1, 2, 3, 8], нижний — [2, 6, 7, 9]. Оба строго возрастают после одного обмена.

Пример 2
top=[1, 2, 3], bottom=[4, 5, 6] → 0

Оба ряда уже строго возрастают.

Пример 3
top=[5, 2, 7, 4], bottom=[1, 6, 3, 8] → 2
Ограничения
  • 2 ≤ len(top) = len(bottom) ≤ 10⁵
  • 0 ≤ top[i], bottom[i] ≤ 2·10⁵
  • Добиться возрастания обоих рядов можно
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиВода между стенами СложнаяСамый большой горящий блок СложнаяПрибыль за две сделки СложнаяВсе способы расставить пробелы СложнаяПереход через пещеру Сложная
загружаем Python…
Вход
top=[1, 6, 3, 8], bottom=[2, 2, 7, 9]
Ожидается
1

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 32 теста на сервере, включая скрытые.