一次递增两个数组元素，以便所有元素都等于最大值

Question

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

使其成为最大数组 - 将数组的每个元素转换为等于其最大元素。在上面的例子中，它将是[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. 查找每个数字的重复对，然后查找剩余的单个数字

< li >偶数和奇数的数量应该相等

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

Answer 1

这里有一个简单的算法，应该可以工作。其思想是首先增加最低值：

>

找到最大值。我们称它为最大值。

求最小值。姑且称之为min吧。如果min = max，输出YES。

找到一个值为min的元素并递增它。

找出其他元素的最小值。姑且称之为min吧。如果min = max，则输出NO。

找到一个值为min的元素（前一个元素除外），并将其递增。

转到步骤 2。

Answer 2

这实际上是一个已知的面试/编程竞赛问题，但它通常表示为“给定一个正整数数组，你能一次将它们全部减少到零，两个（或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

更具体的问题陈述

这个问题的一个不幸的特点是，尽管解决方案直观上很简单，但这个解决方案的完整证明相当长。问题的原始陈述已经引起了对短语“max array”的含义的混淆，所以我将尝试给出问题的精确数学描述，然后转换它。这将解释为什么代码对问题执行自然的“贪婪策略”,以及为什么它有效。

原问题:给定一个长度为n的正整数A的零索引数组

贪婪的策略

如果性能不是问题，那么这个问题的“贪婪”或暴力解决方案就是从A中选择两个最小的元素并递增它们，重复此操作，直到A中除一个元素之外的所有元素都等于max（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)的元素之间的差距之和(我们可以称之为< code>total_needed)是奇数，则任务是不可能的。同样正确的是，我们可以在不改变答案的情况下对问题应用以下变换:

新问题：设M=max（A）。变换A[i]后设B为A-

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

设Max_B = 最大值（B），设Sum_B = 总和（B）。由于我们知道如果Sum_B很奇怪，则不存在解决方案，因此我们可以假设从现在开始Sum_B是均匀的。有两种可能性：

< li> Max_B

要证明（2），证明两件事就足够了：i. ifMax_B

第一个陈述的证明是代数操作和案例分析，这并不令人惊讶，所以我将从这个已经很长的证明中省略。第一个Python代码片段现在可以理解为检查< code>total_needed的奇偶校验，以及我们是否处于上述情况(1)或(2)。

编辑：代码的原始发布版本在最后一行有一个错误，与解释和证明中的等式相比，使用了不正确的变量名和翻转的不等式符号。感谢用户“打破不那么糟糕”发现了这一点。