一次增加两个数组元素，使其全部等于最大值

Question

给定任何自然数数组，例如： [2, 1, 2, 3] 查找数组是否可以转换为 Max 数组（打印 - “YES”），否则（打印 - “NO”）

使其成为最大数组 - 将数组的每个元素转换为等于其最大元素。在上面的例子中它将是 [3, 3, 3, 3] 但遵循这些规则 -

1. 一次将任意两个元素增加 1（正好是 2 个元素。一次不能增加一个或两个以上元素）
2. 多次执行此操作，直到将每个元素转换为等于最大元素（如果可能，则打印“YES”，否则“NO”）

示例输入： [2,1,2,3]

预期输出： “是”

解释：

步骤 1：将第一个和第二个元素增加 1 -

[3,2,2,3]

步骤 2：将第二个和第三个元素增加 1 -

[3,3,3,3]

任何人都可以指出解决方案 - 任何链接、类似的问题、模式或解决方案吗？谢谢

编辑：

我尝试过这种方法来解决它 -

1. 找到最大值并将其删除
2. 查找每个数字的重复对，然后查找剩余的单个数字

• 偶数和奇数的数量应该相等

但不能完全得到正确的结果。

Answer 1

这实际上是一个已知的面试/编程竞赛问题，但它通常表现为“给定一个正整数数组，你能一次将它们全部减少到零、两个（或 k 个）吗？”

有一个简单的解决方案：我们只需要检查是否能够以二为步长达到所需的和（即检查奇偶性），以及当所有其他数字都达到最大值时，最小的数字是否可以达到最大值。

def is_possible(nums: List[int]) -> bool:
    smallest, largest = min(nums), max(nums)
    total_needed = sum(largest - x for x in nums)
    if total_needed % 2 == 1:
        return False
    return 2 * (largest - smallest) <= total_needed

这给出：

assert is_possible([6, 6, 10])    == True
assert is_possible([2, 1, 2, 3])  == True
assert is_possible([1, 5, 5, 9])  == True
assert is_possible([1, 2, 9])     == False
assert is_possible([1, 4, 9, 10]) == False
assert is_possible([1, 6, 6, 9])  == False

更具体的问题陈述

这个问题的一个不幸的特点是，尽管解决方案直观上很简单，但该解决方案的完整证明相当长。该问题的原始陈述引起了对“最大数组”一词含义的混淆，因此我将尝试给出该​​问题的精确数学描述，然后对其进行转换。然后，这将解释为什么代码针对该问题实施自然的“贪婪策略”，以及为什么它有效。

原始问题：给定一个长度为 n > 1 的正整数 A 的零索引数组，您可以执行以下操作任意多次：选择两个不同的索引i, j with 0 <= i < j < n，使得A[i] < max(A) and A[j] < max(A)，并递增A[i] and A[j]。确定是否可以使所有数组元素相等。

贪婪策略

如果不考虑性能，此问题的“贪婪”或暴力解决方案是从 A 中选择两个最小的元素并递增它们，重复此操作，直到 A 中的所有元素或除一个元素外的所有元素等于最大（A）。如果恰好有一个元素不等于 max(A)，我们就失败并且任务是不可能的（该语句需要证明）；否则这显然是可能的。

def is_possible_brute_force(nums: List[int]) -> bool:
    largest = max(nums)
    nums.sort()

    while nums[0] != largest:
        first = nums.pop(0)
        second = nums.pop(0)
        if second == largest and first != largest:  # If exactly one number not max
            return False
        bisect.insort(nums, first+1)
        bisect.insort(nums, second+1)

    return all(x == largest for x in nums)  # Always true

我们的目标是模拟此过程的结果，而不是实际执行。我们可以立即观察到，如果 A 的元素与 max(A) 之间的间隙之和（我们可以称之为），则任务是不可能完成的total_needed。我们确实可以在不改变答案的情况下对问题应用以下转换：

新问题：设 M = max(A)。令 B 为变换 A[i] -> M - A[i] 后的 A。现在，我们允许的操作是递减 B 的两个不同索引，我们的目标是达到零数组。

用 B 和减量来思考会更容易。你可能想到的第一个策略是：反复递减B中最大的两个元素，即贪心策略。事实证明，这个策略是最优的，只要有解决方案就可以找到解决方案。

让Max_B = max(B)让Sum_B = sum(B)。由于我们知道如果 Sum_B 为奇数则不存在解，因此我们可以从这里假设 Sum_B 为偶数。有两种可能：

1. Max_B > Sum_B - Max_B。在这种情况下，无论我们做什么，在执行 Sum_B - Max_B 递减之后，除了 Max_B 之外的所有元素都为零，因此不可能有解。
2. Max_B <= Sum_B - Max_B。在这种情况下，解决方案总是可能的。

要证明(2)，只需证明两件事即可： i．如果Max_B <= Sum_B - Max_B，那么在减少两个最大的元素之后，我们仍然有Max_B <= Sum_B - Max_B新的数组。二. 唯一不可能移动但 B 不为零的配置是 B 中恰好有一个元素不为零；在这种情况下，Max_B > Sum_B - Max_B

第一个陈述的证明是代数运算和案例分析，这并不令人惊讶，因此我将从这个已经很长的证明中省略它。第一个Python代码片段现在可以理解为检查 的奇偶性total_needed，以及我们是否处于上述情况（1）或（2）。

编辑：与解释和证明中的方程相比，最初发布的代码版本在最后一行有一个错误，使用了不正确的变量名称和翻转的不等号。感谢用户 Breaking Not So Bad 捕捉到了这一点。