题目描述

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

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

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

样例

输入：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] 完成

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

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

限制

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

算法

(数学) $O(n \log M \log n)$

1. 维护一个大根堆，同时维护当前所有数字的和。当前数组中最大的数字一定是最后一次修改的位置。
2. 每次出堆最大的数字 $x$，判断如下情况：
   • 如果 $x$ 等于 $1$，则返回 true；
   • 如果 $x \le sum - x$，则返回 false（最大的数字小于等于其他的数字的和，这意味着这个位置上原来的数字小于等于 $0$）。
   • 如果 $x \% (sum - x) = 0$ 并且 $sum - x > 1$，返回 false。
3. 否则，计算 $y = x \% (sum - x)$，更新 $sum$ 为 $sum - (x - y)$，然后将 $y$ 插入堆，继续以上的操作。
4. 其实，这个过程类似于求最大公约数的辗转相除法，我们每次需要求出来最大的数字最小可能的值。

时间复杂度

• 用 $O(n)$ 的时间构造堆。
• 然后，每个数字可能需要 $O(\log M)$ 的时间变为 1，同时维护堆的代价为 $O(\log n)$，故总时间复杂度为 $O(n \log M \log n)$。其中，$M$ 为最大的数字的值。

空间复杂度

• 需要 $O(n)$ 的额外空间存储堆。

C++ 代码

#define LL long long

class Solution {
public:
    bool isPossible(vector<int>& target) {
        int n = target.size();
        if (n == 1 && target[0] > 1)
            return false;

        priority_queue<int> q(target.begin(), target.end());

        LL sum = 0;
        for (int x : target)
            sum += x;

        while (!q.empty()) {
            int x = q.top();
            q.pop();

            if (x == 1)
                return true;

            LL rest = sum - x;

            if (x <= rest)
                return false;

            int y = x % rest;

            if (y == 0 && rest > 1)
                return false;

            sum = rest + y;
            q.push(y);
        }

        return true;
    }
};