1354：多次求和构造目标数组（2014 分）

力扣第 176 场周赛第 4 题

题目

给你一个整数数组 target 。一开始，你有一个数组 A ，它的所有元素均为 1 ，你可以执行以下操作：

• 令 x 为你数组里所有元素的和
• 选择满足 0 <= i < target.size 的任意下标 i ，并让 A 数组里下标为 i 处的值为 x 。
• 你可以重复该过程任意次

如果能从 A 开始构造出目标数组 target ，请你返回 True ，否则返回 False 。

示例 1：

输入：target = [9,3,5]
输出：true
解释：从 [1, 1, 1] 开始
[1, 1, 1], 和为 3 ，选择下标 1
[1, 3, 1], 和为 5， 选择下标 2
[1, 3, 5], 和为 9， 选择下标 0
[9, 3, 5] 完成

示例 2：

输入：target = [1,1,1,2]
输出：false
解释：不可能从 [1,1,1,1] 出发构造目标数组。

示例 3：

输入：target = [8,5]
输出：true

提示：

• N == target.length
• 1 <= target.length <= 5 * 10^4
• 1 <= target[i] <= 10^9

相似问题：

• 2335：装满杯子需要的最短总时长（1360 分）

分析

• 反过来考虑，最后一步得到的数必然是最大的那个，设为 x
• 设最后的总和为 s，那么最后一步之前 x 应该是 x-(s-x)
• 依此一步步反推，直到 x<=s-x 为止，此时判断 x 是否为 1 即可
• 注意到假如 x 减了多次，每次的 s-x 是恒定的，所以可以用除法加速这个过程

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def isPossible(self, target: List[int]) -> bool:
        pq = sorted(-x for x in target)
        s = sum(target)
        while pq:
            x = -heappop(pq)
            if x<=s-x or s-x==0:
                return x==1
            y = (x-1)%(s-x)+1
            s += y-x
            heappush(pq,-y)

19 ms