如果这个序列的每个元素都可以被 4
整除,那么这个整数序列是美丽的。给你一个序列 a1, a2, ..., an
。在一个步骤中,您可以选择该序列的任意两个元素,将它们从序列中移除并将它们的和添加到序列中。计算使给定序列变得漂亮所需的最少步骤数,否则打印 -1
如果这不可能。
for i in range(int(input())):
n=int(input())
arr=list(map(int,input().split()))
if((sum(arr))%4)!=0:
print(-1)
continue
else:
counter=[]
for i in range(n):
if arr[i]%4!=0:
counter.append(arr[i])
else:
continue
x=sum(counter)
while(x%4==0):
x=x//4
print(x)
我的方法:如果数组的总和不能被 4
整除,那么如果数组 mod 4
的总和等于零我计算数组中 4 的模数不等于零的元素并将它们附加到列表中然后找到列表的总和并将总和除以 4 直到它的商模 4 不等于零。我是什么我在这里做错了吗?
编辑:我有一个运行良好的脚本
for i in range(int(input())):
n=int(input())
arr=list(map(int,input().split()))
count1=0
count2=0
count3=0
summ=0
for i in range(n):
x=arr[i]%4
summ+=x
if x==1:
count1+=1
if x==2:
count2+=1
if x==3:
count3+=1
if (summ%4)!=0:
print(-1)
continue
else:
if count2==0 and count1!=0 and count3==0:
tt=count1//4
print(3*tt)
if count2==0 and count1==0 and count3!=0:
tt=count3//4
print(3*tt)
if count2%2==0 and count1==count3:
print(count2//2+count1)
flag1=min(count1,count3)
flag2=abs(count1-count3)
if count2%2==0 and count1!=count3:
flag3=flag2//4
flag4=flag3*3
print(count2//2+ flag1+ flag4)
if count2%2!=0 and count1!=count3:
flag3=flag2-2
flag4=flag3//4
flag5=flag4*3
print(((count2-1)//2)+flag1+flag5+2)
最佳答案
首先是一些观察:
- 为了 4 整除性,我们可以用除以 4 的余数替换所有数字,因此我们只需要处理值 0、1、2 和 3。
- 顺序无关紧要,计算零、一、二和三就足够了。
- 有一对立即给出可被 4 整除的和:(1, 3) 和 (2, 2)。这样一对的每一个存在都需要一个步骤。
- 有三元组 (1, 1, 2) 和 (3, 3, 2) 需要两个步骤。
- 有四元组 (1, 1, 1, 1) 和 (3, 3, 3, 3) 需要三个步骤。
算法:
- 计算余数0(可省略)、余数1、余数2、余数3。
- 如果总和(来自计数)不能被 4 整除,则没有解决方案。
- 对于上述所有 N 元组,找出它们符合计数的频率;加上最终的步数,从计数中减去消耗的数字。
最后,remainder-1、remainder-2 和 remainder-3 计数应为零。
关于python - 美丽的序列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47967633/