[贪心][数学]leetcode6144：将数组排序的最少替换次数(hard)_leetcode 数组 替换最小次数

题目：

题解：

思路：贪心+数学

代码如下：

using LL = long long;
class Solution {
public:
    long long minimumReplacement(vector<int>& a) {
        LL res=0;
        // 记录当前元素拆分出来的最小数字
        int mi=a.back();
        for(int i=a.size()-1;i>=0;i--)
        {
            // 操作次数 k = x-1，其中 x = (a[i]-1)/m+1，表示为拆分出来的数字个数，所以 k = (a[i]-1)/m
            // 这里是不需要进行判断 a[i] 与 mi 的大小关系；是因为 a[i]<=mi 时，k 算出来为 0，a[i] 是不需要进行拆分的；只有 a[i]>m 时，才需要进行拆分的；
            int k=(a[i]-1)/mi;
            res+=k;
            // 当前元素拆分出来的最小数字为 a[i]/x
            mi=a[i]/(k+1);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19