arrays - 一次递增两个数组元素，使它们都等于最大值

Question

给定任意自然数数组，例如:[2, 1, 2, 3]查找数组是否可以转换为 Max 数组(打印 - "is")或如果不能(打印 - “否”)

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

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

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

预期输出:"is"

解释:

第 1 步:将第一个和第二个元素递增 1 -

[3, 2, 2, 3]

第 2 步:将第二个和第三个元素递增 1 -

[3, 3, 3, 3]

谁能指出解决方案 - 任何链接、类似问题、模式或解决方案？谢谢

编辑:

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

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

• 偶数和奇数应该相等

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

Answer 1

这其实是一个已知的采访/programming contest问题，但它通常呈现为“给定一个正整数数组，你能否一次将它们全部减少为零、两个(或 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

更具体的问题陈述

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

Original Problem: Given a zero-indexed array of positive integers A of length n > 1, you are allowed to perform the following operation any number of times: Choose two distinct indices i, j with 0 <= i < j < n, such that A[i] < max(A) and A[j] < max(A), and increment A[i] and A[j]. Determine whether you can make all of the array elements equal.

贪心策略

这个问题的“贪婪”或蛮力解决方案，如果性能不是问题，将是从 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) 之间的间隙之和为 total_needed，我们可以立即观察到该任务是不可能的。 , 很奇怪。我们也可以在不改变答案的情况下对问题应用以下转换:

New Problem: Let M = max(A). Let B be A after the transform A[i] -> M - A[i]. Our allowed operation is now to decrement two distinct indices of B, and our goal is to reach the zero array.

从 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)，只需证明两件事:我。如果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 捕获了这一点。