[TOC]

同学问我一个字节跳动的面试的算法问题

昨晚我的一个同学问了我下面这个问题，说是字节跳动面试的题目：

一根火柴能拆成两份，然后放在原处。
拆了的 还可以再拆
最后保证非下降
问 最少要拆几次
比如 3 5 13 9 12 变成 3 5 6 7 9 12。1次就好了

我的第一感觉是这个或许应该可以线性复杂度解决，很有可能是有贪心策略的。
首先想到的是，应该从后面开始扫起，因为前面的火柴棒显然不能超过后面的火柴棒的长度。

然后我发现来可能需要解决一个问题，如果前面的火柴棒比后面的长，那么怎么切分它合适？

一个自然的想法是要让最短的小棒尽可能长，这样对于前面的小棒而言上限就更大一些。显然长度上限越大越好（至少上限大的不会比上限小的差）。

但是，我发现需要考虑一个问题，虽然这样有利于前面的小棒切分数尽可能少，但是对当前的方案来讲，是否存在一种划分方案，它切分的出来的最短小棒虽然更短一些，但是对于前面的小棒的限制效果是一样的（比如最短长棒尽可能长可以达到10 ，而另一种切分方案最短小棒是8，而前面的小棒长度是7，那么10和8对于7的限制效果是一样的），但是切分出来的小棒数目更少。

稍微一想，直觉上可以看出不存在这种情况。因为如果最短小棒更短的切割方案，直觉上就是切分的比较零碎，那么切分成的小棒数就不应该更少。当然，这个直觉上是对的结论没有那么显然。所以，我后面的分析去证明了这个结论，即尽可能切的数目小的情况下，最短小棒越长， 切分出来的小棒数越少。

所以问题就变成了，知道小棒原始长度和小棒长度上限，让切分成的最短小棒长度尽可能长，最短小棒可以是多长，以及最少要切几次。

于是就有了下面的子问题A和子问题B.

则称为的一种整数划分。

子问题A(a,b)

输入。问在的所有划分中，要求划分中的最大数不超过，最小数最大可以是多少。

即求满足下式最大的.

1. 
2. 
   1. 
      1. 显然
      2. 先划分成k根a和一根r的小棒，之后，我们只需要将根a长度的小棒每根截取加到这个小棒即可构造出最小长度为 的划分方案。
      3. 即
   2. 令,则. 下为证明.
      1. .
         1. 所以拆分的小棒不可能少于 根.
      2. 假设划分成 根小棒，最短的小棒.
         1. 则.
         2. 又.
         3. 显然矛盾。故不存在最小长度大于的方案。
      3. 考虑划分成 根小棒.
         1. 注意有 .
         2. 先根 的小棒，然后剩余的 给 根小棒各自加1即可。
         3. 所以存在一种划分方案最短长度为.

结论

返回.

子问题B(a,b,n)

假设拆分可以使用的数限于 之间的正整数，问 可否实现整数划分，以及划分的根数最小可以是多少?

讨论可以拆分的数 的情况:

也就是说,可由限于 之间的正整数拆分表示的数落在以下有限个区间内：

另外，显然，假设长度可以由上述规则进行整数拆分表示，则，如果,则一定可以划分成的小棒数一定不超过成根。如果则不但可以划分成m根小棒，而且至少需要m根小棒才可以划分。换句话说可能存在多余m根小棒的划分方案，但是一定不存在小于m根的方案，并且一定存在一种方案可以划分成m根。

结论

若 可划分，划分的最小根数d满足,即 .

返回是否可以划分及.

回到原问题

输入数组.

算法

r=a[n] # 长度上限
count = 0
for i = n downto 1
    if a[i] <= r
        r = a[i] # 更新长度上限
        continue
    l = A(r) # 长度下限
    ok, d = B(l,r,a[i]-l) // 事实上ok肯定是true，因为长度下限是由子问题A求出来的。
    count += d
    r = l # 更新长度上限
print(count)

正确性说明

长度为 的小棒,划分长度上限为, 记. 则根据以上关于子问题A、B的讨论知道一定存在一种划分方案.

为了方便讨论，不妨假设划分方案中的数是不下降排列的，即.

假设存在一种划分方案.

由子问题A可知.

因为子问题B是在限定了长度上下限时，求最小划分根数。故有：

显然与假设矛盾。

结论1

这就说明划分方案

既是最短的小棒尽可能长的最佳方案，又是划分划分小棒数尽可能少的最佳方案。

1. 一方面，对于当前小棒来讲，划分小棒数应该尽可能小；

2. 另一方面，显然划分的最短小棒棒长会作为前面的小棒的划分上限，所以这个最短小棒越长越好。

而结论1说明我们的划分方案在上面两个方面努力的结果是一致的，所以我们可以采取算法所述的贪心措施。