本文涉及知識點

堆 優先隊列

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 $lo{g}_{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

相關推薦

我想對大家說的話
《喜缺全書算法冊》以原理、正確性證明、總結為主。
按類別查閱鄙人的算法文章，請點擊《算法與數據匯總》。
有效學習：明確的目標 及時的反饋 拉伸區（難度合適） 專注
聞缺陷則喜(喜缺)是一個美好的愿望，早發現問題，早修改問題，給老板節約錢。
子墨子言之：事無終始，無務多業。也就是我們常說的專業的人做專業的事。
如果程序是一條龍，那算法就是他的是睛

測試環境

操作系統：win7 開發環境： VS2019 C++17
或者 操作系統：win10 開發環境： VS2022 C++17
如無特殊說明，本算法用**C++**實現。