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;
}
};