本文涉及知识点

C++贪心

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

给你一个下标从 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 <= 10⁵
  1 <= nums[i] <= 10⁹

贪心

假定某最优解将nusm[i]拆分成i1个[i2,i3]的数。则i3必须小于等于下一值pre。取i2大。
i2变大，i1会变小或不变。
i2变大。nums[i-1]更容易拆分。
为了i2最大， 如果nums[i]是pre的倍数： 全部拆分成pre。
否则，拆分成cnt =nums[i] / pre+1个数，pre = nums[i]/cnt
时间复杂度：O(n)
pre = INT_MAX
i = n-1 to 0

代码

核心代码

class Solution {
		public:
			long long minimumReplacement(vector<int>& nums) {
				int pre = INT_MAX;
				long long ans = 0;
				for (auto it = nums.rbegin(); it != nums.rend(); ++it) {
					if (*it <= pre) {
						pre = *it;
						continue;
					}
					if (0 == *it % pre) {
						ans += (*it / pre-1);						
					}
					else {
						int cnt = *it / pre + 1;
						ans += (cnt-1);
						pre = *it/cnt;						
					}
				}
				return ans;
			}
		};

单元测试

	vector<int> nums;
		TEST_METHOD(TestMethod11)
		{
			nums = { 3, 9, 3 };
			auto res = Solution().minimumReplacement(nums);
			AssertEx(2LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 1,2,3,4,5 };
			auto res = Solution().minimumReplacement(nums);
			AssertEx(0LL, res);
		}
		TEST_METHOD(TestMethod13)
		{
			nums = { 1,9,2 };
			auto res = Solution().minimumReplacement(nums);
			AssertEx(4LL, res);
		}
		TEST_METHOD(TestMethod14)
		{
			nums = { 12,9,7,6,17,19,21 };
			auto res = Solution().minimumReplacement(nums);
			AssertEx(6LL, res);
		}