2366. 将数组排序的最少替换次数

2366. 将数组排序的最少替换次数

给你一个下表从 0 开始的整数数组 nums 。每次操作中，你可以将数组中任何一个元素替换为 任意两个 和为该元素的数字。

比方说，nums = [5,6,7] 。一次操作中，我们可以将 nums[1] 替换成 2 和 4 ，将 nums 转变成 [5,2,4,7] 。
请你执行上述操作，将数组变成元素按 非递减 顺序排列的数组，并返回所需的最少操作次数。

示例 1：

输入：nums = [3,9,3]
输出：2
解释：以下是将数组变成非递减顺序的步骤：

• [3,9,3] ，将9 变成 3 和 6 ，得到数组 [3,3,6,3]
• [3,3,6,3] ，将 6 变成 3 和 3 ，得到数组 [3,3,3,3,3] 总共需要 2 步将数组变成非递减有序，所以我们返回 2 。

示例 2：

输入：nums = [1,2,3,4,5]
输出：0
解释：数组已经是非递减顺序，所以我们返回 0 。

提示：

1 <= nums.length <= 1e5
1 <= nums[i] <= 1e9

解析：

• 使用倒序+贪心策略
• 为什么使用倒序？因为最后一个数一定肯定不会分解，并且前一个数是否分解、最少分解几次可以根据后一个数决定。
• 例如：3 9 3；3一定不会分解，9由于大于3需要分解，需要分解几次就需要贪心策略了。
• 我们想要的是分解的次数尽量小，同时还要保证分解之后最前边一个数尽量大。
• 例如：28 9–>分解为 7 7 7 7 9肯定是优于5 5 9 9 9的，次数一样，7>5
• 贪心来了，我们可以枚举分解次数，
• 假如分解一次28/2=14，最大值>9不行；
• 分解2次28/3=9…1，肯定有个数为10也不行；
• 分解3次，28/4=7，可以；
• 因此，可以枚举最大次数来确定答案。同样可以证明分解四次优于分解五次，分解五次数小了，次数多了。肯定分解四次最优。
• 难道我们要从1开始枚举吗？其实是不需要的，可以从nums[i]/nums[i+1]开始枚举，最少次数就是max(nums[i]/nums[i+1],1).

class Solution {
    typedef long long ll;
public:
    // 倒序：最后一个数肯定不用分解。贪心保证后边尽量大
    long long minimumReplacement(vector<int>& nums) {
        ll res=0;
        int n=nums.size();
        for(int i=n-2;i>=0;i--){
            if(nums[i]>nums[i+1]){
            	// 这里cnt表示的是分解之后数的个数，也就是cnt=分解次数+1
            	// 最少分解次数为1
                int cnt=max(nums[i]/nums[i+1],2);
                // 枚举分解次数（这里应该可以用二分枚举）
                // 30/4=7...2；最大值为8，30-->7 7 7+1 7+1相当于将2补给后边两个7
                while(true){
                    if((nums[i]/cnt+(nums[i]%cnt==0?0:1))<=nums[i+1])
                        break;
                    else 
                        cnt++;
                }
                res+=cnt-1;
                // 更新当前位置的值
                nums[i]=nums[i]/cnt;
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28