使阵列均匀？

Question

您将得到一个由N个整数组成的数组。如果使用以下操作使阵列完整，那么使整个阵列均匀所需的最小操作数是多少

注意：可以证明这总是可能的

操作

选择一个索引

并执行以下操作：

p=A[i]+A[i+1]；Q=A[i]-A[i+1]

A[i]=p；A[i+1]=Q

整项质询的修正案

这是我的密码

for i in range(int(input())):
    N=int(input())
    arr=list(map(int,input().split()))
    dic=[i for i in range(N) if arr[i]%2!=0 ]
    value=0
    for i in range(len(dic)-1):
        k=dic[i+1]-dic[i]
        value+=k
    print(value)

测试用例

testcase1:
         N=6
         arr= 1 6 4 3 4 2
         my output = 3
         expected output = 4

我不明白为什么在这个测试用例中需要四个操作，因为它只需要三个操作

  testcase 2:
           N=6
           arr = 1 6 4 3 5 2
           my output = 4
           expected output =3

在这个测试用例中，无论我们应用了多少个操作，所有整数都不会转换成偶数

如果有人能告诉我testcase2是如何在三个操作中完成的

testcase1将在四个操作中完成

我做错了吗

它可以通过位操作来解决

Answer 1

下面是一个代码，您可以尝试解决您的问题

def countOperations(arr, n) :
 
    count = 0;
 
    # Traverse the given array
    for i in range(n - 1) :
 
        # If an odd element occurs
        # then increment that element
        # and next adjacent element
        # by 1
        if (arr[i] & 1) :
            arr[i] += 1;
            arr[i + 1] += 1;
            count += 2;
 
    # Traverse the array if any odd
    # element occurs then return -1
    for i in range(n) :
        if (arr[i] & 1) :
            return -1;
 
    # Returns the count of operations
    return count;
 
if __name__ == "__main__" :
 
    arr = [ 2, 3, 4, 5, 6 ];
    n = len(arr);
    print(countOperations(arr, n));

Answer 2

in this testcase all the integers will not be converted into even number no matter how many operations we applied .

• 是的，他们可以。请参阅下面的解决方案

这个想法很简单。我没有使用过任何操作，但我会这样做

• 奇数+/-奇数=偶数
• 奇数+/-偶数=奇数

对于一个i，如果A[i]是偶数，我就不在乎了。考虑所有{{CD1}}，这样^ {< CD2}}是奇数。

• 如果A[i+1]是奇数，那么在一次运算中，P=odd+odd和Q=odd-odd都是偶数。我将把计数增加1
• 如果A[i+1]是偶数，那么P=奇数+偶数，Q=奇偶，两者都是奇数。我做过一次手术。现在，我有两个机会，再做一次手术，我可以让两个机会均等。所以，我将把计数增加2

if someone could show me how come testcase2 is done in three operation .

• 操作1：[1 6 4 3 5 2]->[7 -5 4 3 5 2]，A[0] = A[0] + A[1]，A[1] = A[0] - A[1]
• 操作2：[7 -5 4 3 5 2]->[2 12 4 3 5 2]，A[0] = A[0] + A[1]，A[1] = A[0] - A[1]
• 操作3：[2 12 4 3 5 2]->[2 12 4 8 -2 2]，A[3] = A[3] + A[4]，A[4] = A[3] - A[4]

can it be solved with bit manipulation.

• 我认为你可以，除此之外，我不这么认为

下面是一个可能的实现：

def count_ops(A,n):
    count = 0 
    i = 0 
    done_last = False
    while(i < n-1):
        if(A[i]%2 == 0):
            i+=1
            continue
        if(i == n-2):
            done_last = True
        if(A[i+1]%2 == 0):
            count += 2
        else:
            count += 1
        i += 2
    if(not done_last):
        if(A[n-1]%2 == 1):
            count += 2
    print(count)
    return count

注意done_last标志，我将让您自行决定