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

https://leetcode.cn/contest/biweekly-contest-84/problems/minimum-replacements-to-sort-the-array/

这个问题，我最开始思路是正确的，使用贪心算法（虽然我也没有办法证明）。但是实现拆分的时候实现错误了，接着就把问题复杂化做了许多尝试，最后重新绕回来。

贪心算法就是，从后往前考虑，假设相邻元素是 [x, y]

• 如果 x <= y, 那么不需要进行任何处理
• 如果 x > y, 那么就需要对x进行拆分，确保最大值不超过y.

我最开始实现方法是，假设 t=x//y,

• 那么先将(t-1)份拆除出去，则到 z=x-y*(t-1)
• 如果 z <= y, 那么不做任何处理
• 否则将z进行对半分

之前没有接触过类似问题，所以就使用这个“简单并且朴素”的算法来处理。但是结果其实不对，

• 考虑[45,10]这个情况
• 如果按照上面算法处理，那么就是 z=15, 那么拆分之后就是 [7,8,10,10,10]
• 但是其实可以均分成为 [9,9,9,9,9]

所以正确的思路还是进行均分尝试：可能不需要while, 循环1-2次就好了。

def fix(x, y):
    t = x // y
    while True:
        z = x // t
        rem = x % t
        z2 = z
        if rem:
            z2 += 1
        if z2 <= y:
            return z, t - 1
        t += 1

之前复杂化的思路是下面这样的

• 先找到整个区间的最小值num[i] = x（我们不可能对最小值进行切分）
• 然后处理这个最小值的前半段nums[:i]，因为前半段不能超过x
• 然后对剩余区间进行处理，为了加快最小值寻找可以进行预处理

但是有个比较恶心的情况，比如 [ …. 3, 5, .. 4]

• 假设我们先处理 […3]这段
• 然后处理 [5..4]这段的时候，我们需要对5进行拆分
• 不管是拆分成为[2,3], [1,4] 都是不满足对3的要求的
• 这样我们就要对之前的段重新进行拆分，这个就复杂了。