把阵列弄平？
把阵列弄平？
提问于 2021-06-16 06:30:27
给出N个整数的数组A。如果使用以下操作使数组完整，那么使整个数组均匀所需的最小操作数是多少？
注意事项：可以证明这始终是可能的。
操作
选择一个索引
并执行手术：
P=Ai+Ai+1；q=Ai+1；
Ai=P；Ai+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将在四次手术中完成。
我是不是做错了
可以通过位操作来解决这个问题。
回答 2
Stack Overflow用户
回答已采纳
发布于 2021-06-18 07:01:55
在这个测试用例中，不管我们应用了多少个操作，所有整数都不会被转换成偶数。
- 是的，他们可以。见下面的解决方案。
这个想法很简单。我没有用过任何手法，但我会这样做，
- 奇+/-奇数=偶数
- 奇+/-偶数=奇数
对于一个i，如果A[i]是平的，我不会在意。考虑所有的i，例如A[i]是奇怪的。
- 如果Ai+1是奇数，则P= odd+odd和q=奇数，在一个运算中都是偶数.我会把数目增加1。
- 如果Ai+1是偶数，我有P=odd+even和Q=奇数-偶数，都是奇数。我做过一次手术。现在，我有两次机会，再做一次手术，两次手术我都能做到。所以，我会把数量增加2。
如果有人能告诉我为什么testcase2是在三次手术中完成的。
- 操作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]
可以通过位操作来解决这个问题。
- 我想你可以使用逐位操作检查奇偶，除此之外，我不这么认为。
以下是一个可能的实现：
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标志，我将由您来计算。
Stack Overflow用户
发布于 2021-06-16 07:05:42
以下是您可以尝试解决问题的代码。
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));页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/67997451
复制相关文章
相似问题
腾讯云开发者
