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

Question

给定任意自然数数组，例如：[2, 1, 2, 3] 查找 array 是否可以转换为 Max array (print- "YES") 或者如果不能 (print - "NO")

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

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

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

预期输出： “是”

解释：

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

[3, 2, 2, 3]

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

[3, 3, 3, 3]

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

编辑：

我试过这个方法解决了-

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

偶数和奇数应该相等

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

Answer 1

这是一个应该有效的简单算法。这个想法是首先增加最低值：

求最大值。我们称它为最大值。
求最小值。让我们称之为分钟。如果 min = max，输出 YES.
找到一个值为 min 的元素并递增它。
求其他元素的最小值。让我们称之为分钟。如果min = max，输出NO.
找到一个值为 min 的元素（除了前一个元素）并递增它。
转到步骤 2。

Answer 2

这实际上是一个已知的面试/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

更具体的问题陈述

这个问题的一个不幸的特点是，尽管直观上很简单的解决方案，这个解决方案的完整证明相当长。问题的原陈述引起了短语'max array'的含义混淆，所以我将尝试对问题给出精确的数学描述，然后对其进行转换。然后这将解释为什么代码正在为问题实现自然 'greedy strategy'，以及为什么它有效。

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.

贪心策略

这个问题的 'greedy' 或暴力解决方案，如果性能不是问题，将是 select 来自 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 从这里开始是偶数。有两种可能：

Max_B > Sum_B - Max_B。在这种情况下，无论我们做什么，在执行 Sum_B - Max_B 自减后，除 Max_B 之外的所有元素都为零，因此无解。
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 抓住了这个。

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

Increment two array elements at a time so all equal the max value

arrays

algorithm

data-structures