【优先队列】个人练习-Leetcode-1354. Construct Target Array With Multiple Sums

题目链接：https://leetcode.cn/problems/construct-target-array-with-multiple-sums/

题目大意：给出一个数列target[]。从一个长度与target[]相同，所有元素均为1的数列arr[]出发，每次可以将arr[]某个位置的元素替换为当前arr[]所有元素之和。判断经过若干次操作后arr[]是否能变为target[]。

思路：从target[]反向推断，能否变为元素全为1的数列。因为每次操作都会使得新改变的元素是所有元素中最大的，因此将target[]排序后，最大的那个元素一定是最后一次操作变化而来的。

为了方便得到最大元素，使用优先队列，用大顶堆来维护，这样顶部元素就是最大，非常方便。

每次针对最大元素，让其减去【其余元素之和】【的若干倍】（因为最大元素可能是操作好几次得来的，比如[1, 1, 5]）。操作直到无法再进行操作为止。最后查看堆顶元素，如果不是1那么肯定返回false，否则返回true。

注意点：如果在做%=操作时，很有可能出现top变为0的情况（比如[1, 1, 10]），此时其实说明无法做到转换，可以返回false。一开始我将其改成了-=，但发现这样会超时，比如[1, 1000000000]，自减的话要操作太多次，并且其实无法避免上述问题（比如[1, 1, 2]）。后来为了避免除以0的操作，就让其加回到大于0。

完整代码

class Solution {
public:bool isPossible(vector<int>& target) {long long sum = 0;priority_queue<int, vector<int>, less<int>> q;for (auto x : target) {sum += x;q.push(x);}while (1) {int top = q.top();sum -= top;if (sum == 0)break;if (top > sum) {top %= sum;if (top == 0)top += sum;sum += top;q.pop();q.push(top);}elsebreak;}if (q.top() == 1)return true;elsereturn false;}
};