相对排序，交换次数尽可能少 [英] Relative sorting with minimum possible swaps

问题描述

问题陈述: 给定A和B的数组有两个.我们需要打印第i个元素的最小互换数b/w，以便两个数组都将严格增加.

Problem Statement: There are two arrays given A and B. We need to print the number of minimum swaps b/w i'th elements such that the both array will become strictly increasing.

如果数组已经严格增加，则打印0. 如果不可能严格增加数组，则打印-1.

if arrays are already strictly increasing then print 0. if arrays are not possible to become strictly increasing then print -1.

仅第ith个元素A可以与B的第ith个元素交换.

only ith element A can be swapped with ith element of B.

这些元素可能会出现多次.

There is a possibility that the elements may occur more than once.

例如:
输入:

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

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

输出
2

通过将7和8与10& 11.或将8和9与4& 5.

By swaping 7 and 8 with 10 & 11. OR by swaping 8 and 9 with 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)

我的代码说明: 我正在检查1st是否在数组A中严格增加.如果否:则检查B的第i个元素是否大于当前元素，如果是，则检查B的第i个元素是否大于当前元素，然后再检查B的第(i-1)个元素是否小于或小于交换swap的元素答:

My code Explanation: I am checking 1st whether in Array A it is strictly increasing or not. If no: then checking is ith element of B is greater than the current if yes it is greater than ith element of A then one more check if (i-1)th element of B is smaller or not if smaller than swap the element of A.

类似的方法将应用于B.

similar method will be applied to B.

最后检查A&交换后B严格增加.如果是，则打印计数，否则打印-1.

Last check A & B are strictly increasing after swapping. if yes print count else print -1.

我的代码将失败还是正确的方法的任何测试用例? 还有其他方法可以解决此问题吗?

Any test case where My code will fail or is it a correct approach? Any other approach to solve this problem?

推荐答案

您的代码将失败

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

当正确的最小交换数为1时返回2.

returning 2 when the correct minimum number of swaps is 1.

我们可以形成递归f(i, swap)来表示可达到索引i的最小交换次数，其中swap是布尔值，表示是否要交换索引i的元素:

We can form a recurrence f(i, swap) to represent the minimum number of swaps achievable up to index i where swap is a boolean representing if the elements at index i are to be swapped:

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).)

这篇关于相对排序，交换次数尽可能少的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！