2366. Minimum Replacements to Sort the Array

給定一個陣列 nums ，可以透過將元素 nums[i] 替換成兩個元素 a,b ，但必須滿足 a+b = nums[i] 。請利用上面提到的分解方法，找出最小的分解次數使得陣列為非嚴格遞增。

這是一個 greedy 的問題，不得不說有偷懶一下， leetcode 給的 hint 起了很大的作用。如果我從最前面開始分解，這樣當我後面有元素被分解時，我還需要往前檢查順序有沒有亂掉，但如果我從最後面往前迭代，代表我只要不超過後一個元素大小，那我分解後的順序就可以保持由小到大。

那再來就是我應該要怎麼分解 ? 可以觀察一下 nums= [3,9,3] ，如果我要分解 nums[1] ，勢必最大只能是 3 ，那我應該會分解幾次 ? 這裡應該要考量整除和非整除的情況，如果整除 9 = 6+3 = 3+3+3 剛好會是 9/3–1 ，其實想成我會要幾個 3 ，但因為最後一次會分解出兩個 3 所以要少算一次。那如果非整除的話 7=4+3= 1+3+3，就會剛好是 floor(7/3) 。

但這裡有個細節必須注意，以上面的例子7來說不只有一種分解方式7=1+3+3=2+2+3，如果分解成第一種的話，剩下的元素就只能分解成 1 ，反而會增加分解的次數。所以會希望分解後的第一個數字越大越好。

我們應該先考慮 7 應該要被分解成幾堆，也就是 floor(7/3)+1 總共會有三堆，最後一堆至少是 7/3 的餘數。如果我們已知幾堆，那就可以推算每一堆應該至少要有 floor(7 / floor(7/3)+1) 個，這樣就保證分解是平均的(2+2+3)，而不會是第一堆數字很小的情況出現(1+3+3)。

如果還是不太懂可以帶 nums = [12,9,7,6] 的例子跑一次下面的code就知道了。

class Solution {
public:
    long long minimumReplacement(vector<int>& nums) {
        long long opTimes = 0;
        int len = nums.size();
        int prev_number = nums[len-1];
        
        for(int i=len-2; i>=0; i--){
            if(nums[i] > prev_number){
                opTimes += (nums[i]/prev_number);
                if(nums[i] % prev_number != 0){
                   prev_number = nums[i] / ((nums[i]/prev_number)+1);
                }
                else
                    opTimes--;
            }
            else
                prev_number = nums[i];

            // cout << prev_number << " " << opTimes << endl;
            // 
        }
        // cout << endl;
        return opTimes;
    }
};

這次仍然是看 hint + editorial 寫出來的，主要是忽略了上面提到的 7 = 1+3+3=2+2+3 的問題，但了解問題點後就照著自己的想法寫出來了。

Time Complexity: O(n)
Space Complexity: O(1)