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的要求的
- 这样我们就要对之前的段重新进行拆分，这个就复杂了。