Относительная сортировка с минимально возможными перестановками

Question

Постановка задачи: Существует два массива, заданных A и B. Нам нужно напечатать количество минимальных свопов с ч / б элементами так, чтобы оба массива стали строго увеличиваться.

если массивы уже строго увеличиваются, выведите 0. Если массивы невозможно увеличить строго, выведите -1. ​​

только i-й элемент A может быть заменен на i-й элемент B.

Существует вероятность того, что элементы могут встречаться более одного раза.

Например:
Ввод:

t = 7
A = 1 23 8 9 7 8
B = 1 2 3 4 5 10 11

выход
2

Путем замены 7 и 8 на 10& 11. ИЛИ путем замены 8 и 9 на 4 и 5.

Мой код Python3:

t=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

count=0
for i in range(1,t):
    if(A[i]-A[i-1]<=0):
        if(A[i]<B[i]):
            if(B[i-1]<A[i]):
                A[i],B[i]=B[i],A[i]
                count=count+1
for i in range(1,t):
    if(B[i]-B[i-1]<=0):
        if(B[i]<A[i]):
            if(A[i-1]<B[i]):
                A[i],B[i]=B[i],A[i]
                count=count+1   
ans=False
for i in range(1,t):
    if(A[i]-A[i-1]<=0):
        ans=True
        break
    if(B[i]-B[i-1]<=0):
        ans=True
        break   
if(ans):
    print(-1)
else:
    print(count)

Мой код Объяснение: Я проверяю 1-й, действительно ли в Массиве A оно строго увеличивается или нет. Если нет: тогда проверка, является ли i-й элемент B больше, чем текущий, если да, это больше, чем i-й элемент A, тогда еще одна проверка, если (i-1) -й элемент B меньше или нет, если меньше, чем замена элементаA.

аналогичный метод будет применен к B.

Последняя проверка A & B строго увеличивается после замены. если да, выведите счетчик, иначе выведите -1.

---

Любой тестовый случай, когда Мой код не пройден или это правильный подход? Любой другой подход к решению этой проблемы?

Answer 1

На самом деле ваш код должен быть реорганизован несколькими способами. Это будет легко читать. Я рекомендую несколько простых методов:

checkIncrement(list, index) : boolean return true if value at index > index -1 
swap(list1,list2,index) : swap value
getWrapCount(list1,list2) : return number swap

Метод getWrapCount: псевдокод

    size= min_size(list1,list2);
    swapCount=0    
    for index: 1-> size
            if !checkIncrement(list1,index) or !checkIncrement(list2,index)
                swap(list1,list2,index);
                if !checkIncrement(list1,index) or !checkIncrement(list2,index) return -1;//not possible to become strictly increasing then  -1.
                swapCount++;
return (swapCount,size-swapCount);

Сложность будет O (N) в худшем случае и O (1) в лучшем случае.

Answer 2

Ваш код не будет выполнен для

A = [4, 2, 3]
B = [1, 5, 6]

, возвращая 2, когда правильное минимальное количество свопов равно 1.

Мы можем сформировать повторение f(i, swap) для представления минимального количества своповдостижимо до индекса i, где swap - логическое значение, представляющее, следует ли поменять местами элементы с индексом i:

f(i, false) = min(
  f(i - 1, false) if A[i] > A[i-1] and B[i] > B[i-1] else Infinity,

  f(i - 1, true) if A[i] > B[i-1] and B[i] > A[i-1] else Infinity
)

f(i, true) = min(
  1 + f(i - 1, false) if B[i] > A[i-1] and A[i] > B[i-1] else Infinity,

  1 + f(i - 1, true) if B[i] > B[i-1] and A[i] > A[i-1] else Infinity
)

(сложность времени O(n).)