美丽的序列

Question

如果这个序列的每个元素都可以被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的总和等于零，则数组不能是美丽的我计算数组中的元素，其中mod由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)

Answer 1

首先是一些观察：

• 为了4-divisibility，我们可以用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元组，找出它们适合计数的频率;添加结果步数，减去计数消耗的数字。

最后，余数-1，余数-2和余数-3计数应为零。

Answer 2

这是一个O（N）实现，几乎是在Ralf Kleberhoff建议的方向：

from collections import Counter

def beautify(seq):
    # only mod4 is interesting, count 1s, 2s, and 3s
    c = Counter(x % 4 for x in seq)
    c1, c2, c3 = c.get(1, 0), c.get(2, 0), c.get(3, 0)
    steps22, twos = divmod(c2, 2)  # you have either 0 or 1 2s left
    steps13, ones_or_threes = min(c1, c3), abs(c1 - c3)
    if not twos and not ones_or_threes % 4:
        # 3 steps for every quadruple of 1s or 3s
        return steps22 + steps13 + 3 * ones_or_threes // 4  
    if twos and ones_or_threes % 2 == 2:
        # 2 extra steps to join the remaining 2 1s or 3s with the remaining 2
        return steps22 + steps13 + 3 * ones_or_threes // 4 + 2
    return -1

Answer 3

我不完全确定你的问题是什么，但也许你可以改变你的方法来解决问题。你的逻辑似乎很好，但似乎你试图一次性完成所有事情，如果你把它分解成碎片，这个问题会容易得多。它看起来很适合分裂和征服/递归方法。我也冒昧地自己解决这个问题，因为这似乎是一个有趣的尝试问题。

建议如下

你要做的第一件事就是编写一个函数，找到两个数字，它们的总和可以被k整除，并返回它们：

def two_sum(numbers, k):
    n = len(numbers)

    for i in range(0, n):
        for j in range(i+1, n):
            if (numbers[i] + numbers[j]) % k == 0:
                return numbers[i], numbers[j]
    return None

此外，上述功能是O(n^2)，这可以更有效。

其次，你可以编写一个使用上述函数的递归函数，并且有一个基本情况，当列表中的所有数字都被k整除时它停止递归，因此列表变得“漂亮”。这是一种方法：

def rec_helper(numbers, k, count):
    if all(x % k == 0 for x in numbers):
        return count

    # probably safer to check if two_sum() is not None here
    first, second = two_sum(numbers, k)

    numbers.remove(first)
    numbers.remove(second)
    numbers.append(first + second)

    return rec_helper(numbers, k, count + 1)

上述代码的程序

• 基本情况：如果列表中的所有项目当前都可以被k整除，则返回当前累积的count。
• 否则，获得一对整数，其总和可以从k的two_sum()整除
• remove()这两个数字来自列表，而append()将它们列到列表的末尾。
• 最后，再次调用rec_helper()，新的修改列表和count增加1，即count + 1。 count这里是最小步数。

最后，您现在可以编写一个主调用函数：

def beautiful_array(numbers, k):
    if sum(numbers) % k != 0:
        return -1

    return rec_helper(numbers, k, 0)

在继续调用sum()之前，首先检查列表中数字的k是否可以被rec_helper()整除。如果它没有通过这个测试，该函数只返回-1，并且列表不能变得“漂亮”。

上述代码的行为

>>> beautiful_array([1, 2, 3, 1, 2, 3, 8], 4)
3
>>> beautiful_array([1, 3, 2, 2, 4, 8], 4)
2
>>> beautiful_array([1, 5, 2, 2, 4, 8], 4)
-1

注意：上面的代码示例只是建议，您可以随意关注或使用它。它也不处理input()，因为我认为代码中的主要问题是方法。我不想创建一个全新的解决方案来处理您的输入。如果上述代码有问题，或者您不明白，请在下面评论。