Доброго времени суток, недавно я задумался над одной задачей, хочу поделиться с остальными: У вас есть два массива одинаковой длины n, вам нужно посчитать за какое минимальное количество операций обмена двух произвольных элементов первого массива из первого массива можно получить второй. (Элементы первого массива необязательно различны). В поисках эффективного решения Гугл меня ни к чему не привёл. Ясно как решать когда все элементы различны за O(n). Также предположительно есть решение за O(n) и для общего случая, но я не знаю как его проверить. Задача выглядит слишком баянисто. Знает кто как решать такое? Если знаете куда можно сдать, дайте ссылку.
Заранее спасибо!