解Leetcode 2366. Minimum Replacements to Sort the Array

 

這就是個用除法的貪婪演算能解的問題，除法有很難嗎？為什麼列為hard? 給定一個從 0 開始索引的整數陣列 nums。在一次操作中，可以將陣列中的任何元素替換為兩個相加等於該元素的元素。 例如，考慮 nums = [5,6,7]。在一次操作中，我們可以將 nums[1] 替換為 2 和 4，將 nums 轉換為 [5,2,4,7]。 返回使陣列按非遞減順序排序所需的最小操作次數。

只有陣列末端的數字是確定不變的。使用倒序迭代。比較最後和目前的數字。進行以下的除法：

curr=q∗last+r

並計算操作次數，同時更新 last 的值。

需考慮的三種情況：

情況一：q=0 時：last=r（在此情況下 curr!=0 => r!=0）

情況二：r=0 時：使用 (q-1) 次操作，保持 last 不變（將 curr 分成 q 次 last 需要 (q-1) 次操作）

情況三：q!=0 且 r!=0 時：使用 q 次操作，更新 last 為 last-=ceil((last-r)/(q+1))（將 curr 分成 (q+1) 個數字）

python code:

class Solution:
    def minimumReplacement(self, nums: List[int]) -> int:
        op=0
        n=len(nums)
        last=nums[n-1]
        for i in range(n-2, -1, -1):
            q, r=divmod(nums[i], last)
            if q==0:
                last=r
            elif r==0:
                op+=(q-1)
            else:
                op+=q
                last-=((last-r+q)//(q+1)) #-=ceil((last-r)/(q+1))
        return op

https://leetcode.com/problems/minimum-replacements-to-sort-the-array/solutions/3978618/c-python-math-explains-greedy/