【堆优先队列】1354. 多次求和构造目标数组

本文涉及知识点

堆优先队列

LeetCode1354. 多次求和构造目标数组

给你一个整数数组 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⁴
1 <= target[i] <= 10⁹

优先队列

性质一：任何时候构造的数组arr，任意元素都大于>0。下面用数学归纳法证明：
一，初始状态全部为1，符合。
二，假定操作前符合，则操作后也符合。操作前符合，意味者其和大于0，即修改后arr[i]的值大于0。
如果长度为1 ，target[0]等于1则可以构造，否则不能构造。故下文只讨论n >=2。
性质二：根据性质一，n>=2，操作后，最大值一定会越来越大，且不会存在和最大值相同的其它值。
某处操作后，最大值的下标为i1，值为max1,和为sum1。则arr[i1]操作之前的值为 arr[i1] 为： max1 - (sum1-max1)
这样做会超时，比如：[10⁹,1]会执行10⁹次。
改成：

const int canSub = heap.top() - 1;
const int cnt = canSub / (sum - heap.top());
			if (cnt < 1) { return false; }
			const auto old = heap.top() - (sum - heap.top())* cnt;

时间复杂度 ：O(logn $log_{1.5}{\sum(target)}$ )
如果cnt为1 ,总和至少减少三分之一。
cnt为2，至少减少二分之一。
总而言之，每次操作总和会减少1。

代码

将所有数据放到大根堆heap中，sum是大根堆中数据之和。不断执行上述操作，直到 heap.top()为1。
target全为1，也无需特殊处理。
初始heap全部是正数，修改后新增的值也为正数，故:sum1- heap.top()必定大于0。
由于heap中的数只会越来越小，故 heap中的数永远小于等于10⁹,故canSub-1一定在int范围内。

核心代码

class Solution {
public:
	bool isPossible(vector<int>& target) {
		priority_queue<int> heap;
		long long sum = 0;
		for (const auto& n : target) {
			heap.emplace(n);
			sum += n;
		}
		if (1 == heap.size()) { return 1 == heap.top(); }
		while (1 != heap.top()) {				
			const int canSub = heap.top() - 1;
			const int cnt = canSub / (sum - heap.top());
			if (cnt < 1) { return false; }
			const auto old = heap.top() - (sum - heap.top())* cnt;
			sum -= heap.top();
			heap.pop();
			sum += old;
			heap.emplace(old);
		}
		return true;
	}
};

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛