# 2366. Minimum Replacements to Sort the Array
###### tags: `Leetcode` `Hard` `Greedy` `Math`
Link: https://leetcode.com/problems/minimum-replacements-to-sort-the-array/
## 思路
我们用```curr```记录上一个数是什么
如果在从后往前遍历的过程中遇到一个数大于```curr```说明我们要拆分 否则就不用动 更新```curr```就好
拆分的时候如果我们能正好拆成几个```curr```例如```curr=3``` 我们遇到了9就刚好 我们只要```ans+=k-1``` 不用改变```curr```就好
但如果不能刚好拆成几个curr的形式:
我们令```k = nums[i]/curr```,```d = nums[i]%curr```我们要尽量想办法提升```d``` 不然就会逼迫后面拆的更细
所以我们想办法找到一个```p``` ```d+k*p<=curr-p```也就是前面```k```个```curr```每一个都分一点给```d``` 但要保证提升之后的```d```还是比```curr-p```小
这样操作之后，原本的1个```d```和```k```个```curr```，变成了1个```d2```和```k```个```curr2```，其中```d2 = d+p```，```curr2 = curr-p```，且```d2 <= curr2```.

此时这是不是最优的操作呢？并不是。如果```d2 < curr2```，其实我们可以将```k```个```curr2```里面的一部分（而不是整体）拿出1来再贡献给```d2```，必然可以使得```d2```再拉至于```curr2-1```平齐的高度。这是因为之前我们知道，如果```k```个```curr2```每人都再贡献1出来，会导致```d2```会比```curr2-1```还大。所以这意味着，如果贡献出部分的1出来，就能让```d2```与```curr2-1```持平。在这种情况下，```curr2-1```就是拆分出来的```k+1```份里的最小值。

于是，这个回合结束我们将```curr```赋值为```curr2```(如果```d2==curr2```) 或者```curr2-1```(如果```d2<curr2```)
## Code

class Solution {
    public long minimumReplacement(int[] nums) {
        int n = nums.length;
        int curr = nums[n-1];
        long ans = 0;
        for(int i=n-1; i>=0; i--){
            if(nums[i]>curr){
                int k = nums[i]/curr;
                int d = nums[i]%curr;
                if(d==0){
                    ans += k-1;
                }
                else{
                    int p = (curr-d)/(k+1);
                    int x2 = d+p*k;
                    int curr2 = curr-p;
                    if(x2<curr2) curr = curr2-1;
                    else curr = x2;
                    ans += k;
                }
            }
            else{
                curr = nums[i];
            }
        }
        return ans;
    }
}