LeetCode 1354. 多次求和构造目标数组（优先队列+逆向思考）

示例 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

class Solution {
public:
    bool isPossible(vector<int>& target) {
        int i, num;
        long sum = 0, s;
        priority_queue<int> q;//默认大顶堆
        for(i = 0; i < target.size(); ++i)
        {
        	sum += target[i];//总和
        	q.push(target[i]);
        }
        while(q.top() != 1)
        {
        	s = sum-q.top();//剩余的和
        	num = q.top()-s;//栈顶-s，应该为1或者比1大的数
        	if(num < 1)//小于1则false
        		return false;
        	q.pop();//弹出栈顶
        	q.push(num);//把剩余的数再push进去
        	sum -= s;//和减少了s
        }
        return true;
    }
};

class Solution {
public:
    bool isPossible(vector<int>& target) {
        long sum = 0, s, i, num;
        priority_queue<long> q;//默认大顶堆
        for(i = 0; i < target.size(); ++i)
        {
        	sum += target[i];//总和
        	q.push(target[i]);
        }
        while(!q.empty() && q.top() != 1)
        {
        	s = sum-q.top();//剩余的和
        	num = q.top()-s;//栈顶-s，应该为1或者比1大的数
        	if(num < 1)//小于1则false
        		return false;
        	q.pop();//弹出栈顶
            if(num != 1)//等于1就不用再放进去了，节省时间
        	    q.push(num);
        	sum -= s;//和减少了s
        }
        return true;
    }
};

class Solution {
public:
    bool isPossible(vector<int>& target) {
        if(target.size() == 1)
            return target[0] == 1;
        long sum = 0, s, i, num, tp, scale;
        priority_queue<long> q;//默认大顶堆
        for(i = 0; i < target.size(); ++i)
        {
        	sum += target[i];//总和
        	q.push(target[i]);
        }
        while(q.top() != 1)
        {
        	tp = q.top();
        	q.pop();
        	s = sum-tp;//剩余的和
        	scale = max(1,int((tp-q.top())/s));//至少1倍
        	num = tp-scale*s;//栈顶-n*s，应该为1或者比1大的数
        	if(num < 1)//小于1则false
        		return false;
        	q.push(num);
        	sum -= scale*s;//和减少了n*s
        }
        return true;
    }
};